IPO

Hard

You are given a list of projects where projects[i] = [profit, capital], an integer k, and a starting capital w.

You may pick at most k distinct projects. A project can only be started if your current capital is at least its required capital, and finishing it adds its profit to your capital.

Return the maximum capital you can finish with.

The original problem passes two parallel arrays plus k and w. This judge packs each project into a [profit, capital] row so it fits the grid harness — the input box labels the three arguments generically, but they are the projects grid, then k, then w.

Example 1

Input:  projects = [[1,0],[2,1],[3,1]], k = 2, w = 0
Output: 4
Explanation: Start project 0 for profit 1 (capital becomes 1), then project 2 for profit 3, ending at 4.

Example 2

Input:  projects = [[1,0],[2,1],[3,2]], k = 3, w = 0
Output: 6

Constraints

• 1 <= k <= 10^5
• 0 <= w <= 10^9
• 1 <= projects.length <= 10^5
• 0 <= profit, capital <= 10^9