dsa · hard

Capital Deployment Run

A fund starts with w capital and may complete at most k projects. Project i demands at least capital[i] on hand before it can be taken and pays a pure profit of profits[i] on completion (demand and profit are independent). At most one project runs at a time; after each completion the payout raises the on-hand capital immediately.

Arguments

Choose projects greedily to maximise the final capital after at most k completions and return it.

Example

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

Round 1: affordable projects are those with demand 0 — project 1 (profit 1). Take it → capital 1. Round 2: affordable now include projects 2 and 3 (demand 1); take profit 3 → capital 4.

k = 3, w = 0, profits = [1,2,3], capital = [0,1,2] → take profit 1 (capital 1), then profit 2 (capital 3), then profit 3 (capital 6) → 6.

Constraints

1 <= k <= 10^5 0 <= w <= 10^9 1 <= profits.length <= 10^5 profits.length == capital.length 1 <= profits[i] <= 10^4 0 <= capital[i] <= 10^9 Hidden tests include near-max size for this bound; a slower-than-intended solution TLEs.

Examples

Example 1

Input:
2
0
[1,2,3]
[0,1,1]

Expected:
4

Example 2

Input:
3
0
[1,2,3]
[0,1,2]

Expected:
6

Example 3

Input:
1
2
[1,2,3]
[1,1,2]

Expected:
5

Open in the Dojo editor