Problem Brief

Alloy Production

A foundry in Hackerland makes an alloy out of n different metals. In the manufacturing of an alloy, the composition of each metal is fixed, where the required quantity of the nth metal in preparing 1 unit of the alloy is denoted by composition[n]. The company already has stock[n] units of metal in their stock.

The company has a budget to purchase any of the metals if needed. The cost of the nth metal is cost[n] per unit. Find the maximum units of alloys the company can produce by using available stock plus what they can purchase within their budget.

Note: Their supplier has an infinite supply of all metal types.

Function Description

Complete the function findMaximumAlloyUnits in the editor.

findMaximumAlloyUnits has the following parameters:

int composition[n]: the composition of metals in 1 unit of alloy
int stock[n]: the units of metals type that the company has in stock
int cost[n]: the cost of each metal type
int budget: the total money the company can spend

Returns

int: the maximum unit of alloys that can be produced

1Example 1

Input

composition = [1, 2], stock = [0, 1], cost = [1, 1], budget = 3

Output

Explanation

A maximum of 1 unit of alloy can be produced.

- The cost for 1 unit required quantity = [1, 2], stock = [0, 1], extra metal requirements = [1, 1], cost = (1 x 1) + (1 x 3) = 4, which is within the budget.

- The cost for 2 units required quantity = [2, 4], stock = [0, 1], extra metal requirements = [2, 3], cost = (2 x 1) + (3 x 3) = 11, which is beyond the budget.

The answer is 1.

Constraints

Limits and guarantees your solution can rely on.

1 ≤ n ≤ 10^5

1 ≤ budget ≤ 10^9

1 ≤ composition[i] ≤ 10^9

1 ≤ stock[i] ≤ 10^9

1 ≤ cost[i] ≤ 10^9

composition[i] ≤ cost[i] ≤ 10^9