Pick Projects to Grow Capital

A small studio starts with capital coins and can finish at most k projects, one after another. Project i needs at least costs[i] coins in the bank before it can start (the money is only needed, not spent) and adds profits[i] coins when it is finished. Each project can be done at most once.

Write best_capital(k, capital, profits, costs) that returns the most capital the studio can have after finishing at most k projects.

Examples

best_capital(2, 0, [1, 2, 3], [0, 1, 1])
# returns 4

best_capital(3, 0, [1, 2, 3], [0, 1, 2])
# returns 6

best_capital(1, 2, [5, 8], [3, 4])
# returns 2

In the first example only project 0 is affordable at the start, and it brings the capital to 1. Then projects 1 and 2 are both affordable, and project 2 pays more, ending at 4. In the last example no project is affordable, so the capital stays at 2.

Constraints

• 0 <= k <= 100,000 and 0 <= capital <= 10^9
• 0 <= len(profits) == len(costs) <= 100,000
• 0 <= profits[i] <= 10,000 and 0 <= costs[i] <= 10^9
• Looking through every project before each pick is too slow when there are 100,000 projects and 100,000 picks.