IPO: Maximize Capital

You have starting capital w and may finish at most k projects, one after another. Project i needs at least capital[i] to start, and finishing it gives a pure profit of profits[i] (added to your capital). Each project can be done once. Return the largest capital you can have at the end.

For k = 2, w = 0, profits = [1, 2, 3] and capital = [0, 1, 1] the answer is 4.

Examples

Example 1

Input:

find_maximized_capital(2, 0, [1, 2, 3], [0, 1, 1])

Output:

4

Example 2

Input:

find_maximized_capital(3, 0, [1, 2, 3], [0, 1, 2])

Output:

6

Constraints

• 0 <= k <= 100000
• 0 <= w <= 10**9
• 0 <= len(profits) == len(capital) <= 100000
• 0 <= profits[i], capital[i] <= 10**9