A studio starts with c units of capital and may launch at most k of n projects. Project i requires required[i] capital to launch (you can launch it only when your current capital is at least required[i]) and, once launched, immediately adds profit[i] to your capital. Each project can be launched at most once.
The launch strategy is fixed and deterministic: repeat up to k times — among all not-yet-launched projects you can currently afford, launch the one with the highest profit; if several tie for highest profit, launch the one requiring the least capital, and if still tied, the one appearing earliest in the input. Stop early if no project is currently affordable.
Report the final capital.
Input format
Line 1: three integers n, k, and c.
Next n lines: two integers required[i] and profit[i].
Output format
A single integer: the final capital after the launch strategy finishes.
Constraints
- 1 <= n <= 100000
- 1 <= k <= n
- 0 <= c <= 1000000000
- 0 <= required[i] <= 1000000000
- 0 <= profit[i] <= 1000000000