CF500F New Year Shopping
Description
Dohyun is running a grocery store. He sells $ n $ items numbered by integers from 1 to $ n $ . The $ i $ -th ( $ 1
Input Format
N/A
Output Format
N/A
Explanation/Hint
Consider the first sample.
1. At time 1, only the 2nd item is available. I can buy the 2nd item using 3 dollars and my happiness will increase by 5.
2. At time 2, the 1st, 2nd, and 3rd item is available. I can buy the 1st item using 2 dollars, and the 2nd item using 3 dollars. My happiness will increase by 3 + 5 = 8.
3. At time 2, the 1st, 2nd, and 3rd item is available. I can buy the 1st item using 2 dollars, and the 3nd item using 4 dollars. My happiness will increase by 3 + 7 = 10.
4. At time 5, the 1st, 3rd, and 4th item is available. I can buy the 1st item using 2 dollars, and the 4th item using 11 dollars. My happiness will increase by 3 + 15 = 18. Note that I don't need to use the whole budget in this case.