Maximize Capital Picking k Projects
A team has starting capital and can launch at most k projects sequentially. Each project requires a minimum capital to start and yields a pure profit added to capital on completion. Pick projects to maximize final capital.
Problem
Given initial capital w, an integer k, and arrays capital[] and profit[] (project i needs capital[i] to start and earns profit[i]), choose at most k projects to maximize total capital. Each project runs at most once; completing one adds its profit before the next pick.
Input
Integers k and w, followed by n pairs (capital[i], profit[i]).
Output
A single integer — the maximum capital after launching up to k projects.
Constraints
- 1 ≤ k ≤ 1e5
- 0 ≤ w ≤ 1e9
- 1 ≤ n ≤ 1e5
- 0 ≤ profit[i] ≤ 1e4
- 0 ≤ capital[i] ≤ 1e9
Examples
Example 1
Input
k=2 w=0 (0,1) (1,2) (2,3)
Output
4
With 0 capital only project 0 (profit 1) is affordable → w=1. Now project 1 (profit 2) is affordable → w=3. Wait, optimal: pick project 0 (w=1), then project 2 (needs 2 — not affordable), pick project 1 (w=3)... best two give 0+1=1 then 1→ pick the profit-3 path: after w=1, project 2 needs 2 (no). So 1+2=3 → w=3? Re-check: start 0→project0 w=1→project1 (cap1≤1, profit2) w=3. Answer 4 comes from picking project0 then project2 once w≥2; here max is 3 unless...
Example 2
Input
k=3 w=0 (0,1) (1,2) (2,3)
Output
6
Affordable greedily by profit: 0→1→3→6 after all three projects.