IPO

You are given n projects where the ith project has a pure profit profits[i] and a minimum capital requirement capital[i].

You have an initial capital w. When you complete a project, you earn its profit and the profit is added to your total capital.

Pick a list of at most k distinct projects to maximize your final capital, and return the final maximized capital.

Examples

Example 1:

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

Output: 4

Explanation: With initial capital 0, you can only start project 0 (capital requirement 0), earning profit 1. Your capital becomes 1. Now you can start project 1 or 2. Choose project 2 (profit 3) to maximize capital. Final capital = 0 + 1 + 3 = 4.

Example 2:

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

Output: 6

Explanation: Start with project 0 (capital = 0 + 1 = 1), then project 1 (capital = 1 + 2 = 3), then project 2 (capital = 3 + 3 = 6). All three projects are completed.

Example 3:

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

Output: 0

Explanation: All projects require at least capital 1, but you only have 0. No project can be started.

Constraints

• 1 <= k <= 10^5
• 0 <= w <= 10^9
• 1 <= profits.length <= 10^5
• profits.length == capital.length
• 0 <= profits[i] <= 10^4
• 0 <= capital[i] <= 10^9