Maximize Capital by Completing at Most k Projects

A startup has an initial amount of capital w and is choosing which projects to take on before an important funding deadline. There are n candidate projects. Project i has:

• a capital requirement capital[i] — the startup must have at least this much capital on hand to start the project (the capital is a threshold, not a cost; it is not spent), and
• a pure profit profit[i] — completing the project adds this amount to the startup's capital.

The startup can complete at most k distinct projects, one at a time, in any order. After finishing a project, the profit is immediately added to its capital, which may unlock projects that were previously unaffordable. Each project can be completed at most once.

Return the maximum possible final capital after completing at most k projects.

Example 1

k = 2, w = 0
profit = [1, 2, 3]
capital = [0, 1, 1]
Output: 4

Explanation: with capital 0, only project 0 (requirement 0) can be started; completing it raises capital to 1. Now projects 1 and 2 are both unlocked; picking project 2 (profit 3) gives a final capital of 0 + 1 + 3 = 4.

Example 2

k = 3, w = 0
profit = [1, 2, 3]
capital = [0, 1, 2]
Output: 6

Explanation: all three projects can be completed in order of increasing requirement, for a final capital of 1 + 2 + 3 = 6.

Constraints

• $1 \le k \le 10^5$
• $1 \le n \le 10^5$
• $0 \le w \le 10^9$
• $0 \le profit[i] \le 10^4$
• $0 \le capital[i] \le 10^9$
• profit.length == capital.length == n

An efficient solution should run in $O\big((n + k)\log n\big)$ time; an $O(nk)$ brute force will be too slow at the largest inputs.