Company: Uber
Difficulty: medium
Maximize Fleet Upgrade Net Gain A fleet management team is planning vehicle upgrades for the coming year and has a limited operations budget. There are `n` vehicles. For every vehicle `i` (using **0-based** indexing): `upgradeCost[i]` is the cost of upgrading vehicle `i`; `expectedResale[i]` is the value of vehicle `i` after one further year of operation, **if it is upgraded**. You may upgrade any subset of the vehicles, including none of them. A vehicle is either upgraded whole or left alone; it can never be upgraded twice. The **total** cost of the vehicles you upgrade must not exceed `budget`. The net gain of upgrading vehicle `i` is `expectedResale[i] - upgradeCost[i]`. This value may be negative, in which case upgrading that vehicle lowers the total. The net gain of a plan is the sum of the net gains of the vehicles it upgrades; the empty plan has a net gain of `0`. Report the maximum net gain achievable. Input Format The first line contains a single integer `budget`. The second l