Problem Brief

Planning Production

Source image will be included in next update :)

Acme Corp has a number of products that need to be manufactured. However, careful planning must take place before production begins. For each product there is a worst-case cost and an expected cost. Before starting a project, Acme must have at least enough cash on hand to pay the worst-case cost for each product. If every product is produced at expected cost, determine the minimum beginning cash requirement to get all products produced. Products can be produced in any order.

Function Description

Complete the function planProduction in the editor.

planProduction has the following parameter(s):

worstCase[worstCase[0],...worstCase[n-1]]: an array of n integers representing the minimum cash-on-hand to produce the ith product
expected[expected[0],...expected[n-1]]: an array of n integers, representing the expected cost to produce the ith product.

Returns

int: the minimum beginning cash requirement to get all products produced

1Example 1

Input

worstCase = [6, 5, 7], expected = [4, 2, 1]

Output

Explanation

For this case, the optimal order of production is product 2, 1, and 0. Starting with 9 units of cash on hand, they can begin production of product 2 because cash on hand (9 units) ≥ worstCase (7 units). After finishing product 2, they will have 9 - 1 = 8 units of cash on hand. They can then move to product 1 as cash on hand (8 units) ≥ worstCase (5 units). When product 1 is complete, they will have 8 - 2 = 6 units of cash on hand which is enough to start product 0 as cash on hand (6 units) = worstCase (6 units). The minimum amount of cash on hand that will work is 6 - 4 = 2 units. The answer is 9.

Constraints

Limits and guarantees your solution can rely on.

1 ≤ n ≤ 10^5
1 ≤ worstCase[i] ≤ 10^5
1 ≤ expected[i] ≤ 10^5
It is guaranteed that expected[i] ≤ worstCase[i] for every i (0 ≤ i < n).