Maximum Total After K Threshold Gains

You are given an integer k, an integer initial, and two integer arrays gains and thresholds of the same length n.

There are n items. Item i is described by thresholds[i] and gains[i].

You keep a running total that starts at initial. You may take item i only while the running total is at least thresholds[i], and taking it adds gains[i] to the running total.

Each item can be taken at most once, and you take at most k items. You choose the order in which you take them, and you may stop at any time.

Return the largest running total you can end with.

You can assume the answer fits in a signed 32-bit integer.

Examples

Example 1

Input: k = 2, initial = 0, gains = [1,2,3], thresholds = [0,1,1]
Output: 4
Explanation: The total starts at 0, so only item 0 is within reach. Taking it adds 1 and the total becomes 1.
Items 1 and 2 are both within reach now, and item 2 gives the bigger gain, so the total becomes 4.
That is two items, which is the limit.

Example 2

Input: k = 3, initial = 0, gains = [1,2,3], thresholds = [0,1,2]
Output: 6
Explanation: Taking item 0, then item 1, then item 2 keeps the running total at or above each threshold: 0, then 1, then 3, then 6.