IPO (Maximize Capital)

You can complete at most k projects, in any order, to maximize your capital. You start with capital w. Each project has a capital requirement (you can only start it if your current capital is at least that requirement) and a profit (added to your capital once completed). Return the maximum capital achievable after at most k projects.

Example

k = 2, w = 0, profits 1 2 3, capital requirements 0 1 1 Output: 4 (start the $0-requirement project for +1 profit, now have$1, then either $1-requirement project for +2 or +3 — pick the$3 one: total 1 + 3 = 4)

Approach

This is two heaps solving a "maximize X while respecting a constraint on Y" problem: a min-heap of (capital required, profit) pairs sorted by requirement lets you cheaply find every project you can currently afford, and a max-heap of profits lets you cheaply pick the most profitable one among those you can afford. At each of the k rounds: push every newly-affordable project's profit onto the max-heap, then pop the biggest profit and add it to your capital.

Input format

Line 1: k Line 2: w Line 3: number of projects n Line 4: profits, space-separated Line 5: capital requirements, space-separated

Print the final maximized capital.