CF1974E Money Buys Happiness

Being a physicist, Charlie likes to plan his life in simple and precise terms. For the next $ m $ months, starting with no money, Charlie will work hard and earn $ x $ pounds per month. For the $ i $ -th month $ (1 \le i \le m) $ , there'll be a single opportunity of paying cost $ c_i $ pounds to obtain happiness $ h_i $ . Borrowing is not allowed. Money earned in the $ i $ -th month can only be spent in a later $ j $ -th month ( $ j>i $ ). Since physicists don't code, help Charlie find the maximum obtainable sum of happiness.

N/A

N/A

In the first test case, Charlie only gets paid at the end of the month, so is unable to afford anything. In the second test case, Charlie obtains the free happiness in the first month. In the third test case, it's optimal for Charlie to buy happiness in the second month. Even with money left at the end, Charlie could not go back in time to obtain the happiness on offer in the first month.