All problems

IPO

Hard · heap

A young company wants to raise its money before it goes public, by completing some projects. There are n projects. Project i needs at least capital[i] money to start, and once finished it gives a pure profit of profits[i], which is added to the company's money. The requirement is not spent: you only need to hold capital[i] when you start the project, and you keep that money.

The company starts with w money. It can finish at most k projects, one after the other, and each project can be done at most once. It may only start a project if its current money is at least the project's capital value.

Return the largest amount of money the company can have at the end. It is allowed to finish fewer than k projects, or none at all.

Examples

Example 1

Input: k = 2, w = 0, profits = [3, 1, 4], capital = [0, 0, 1]

Output: 7

Projects 0 and 1 are both allowed at the start, and project 0 gives more (3 against 1). With 3 in hand, project 2 is allowed too and gives 4, for a final 7.

Example 2

Input: k = 3, w = 1, profits = [5, 2], capital = [3, 0]

Output: 8

Only project 1 can be started at first, giving 3 in total. Now project 0 is allowed and adds 5, for 8. There are no more projects, even though k allows a third.

Example 3

Input: k = 1, w = 0, profits = [9], capital = [5]

Output: 0

The only project needs 5, which the company does not have.

Constraints