Problem Brief

Max Profit

NEW GRADOA

See IBM online assessment and hiring insights

Find the maximum profit that can be generated for the given amount of money. As the answer can be rather large, report the answer as maxProfit % (10 ^ 9 + 7) where % denotes modulo operator.

Function Description

Complete the function maxProfit in the editor.

maxProfit has the following parameters:

int[] cost: an array of integers representing the cost of each item

int x: the initial amount of money Walker has

Returns

int: the maximum profit that can be obtained modulo (10^9+7)

1Example 1

Input

cost = [3, 4, 1], x = 8

Output

Explanation

2Example 2

Input

cost = [19, 78, 27, 15, 20, 25], x = 25

Output

Explanation

3Example 3

Input

cost = [10, 20, 14, 40, 50], x = 70

Output

Explanation

Some possible combination of items Walker can buy are: She can buy items 0, 1, and 2 for a cost of 44 and obtain a profit of 2 ^ 0 + 2 ^ 1 + 2 ^ 2 = 7 She can buy items 0 and 4 for a cost of 60 and obtain a profit of 2 ^ 0 + 2 ^ 4 = 17 She can buy items 1 and 4 for a cost of 70 and obtain a profit of 2 ^ 1 + 2 ^ 4 = 18 She can buy items 2 and 4 for a cost of 64 and obtain a profit of 2 ^ 2 + 2 ^ 4 = 20 Out of all the possible combinations, the maximum profit obtained is by buying items 2 and 4 for a cost of 64 to obtain a profit of 20.

Constraints

Limits and guarantees your solution can rely on.

1 <= n <= 10^5
1 <= cost[i] <= 10^5
0 <= x <= 10^9