409033: GYM103422 C Charity

You are a very generous man. One day you decided to make a trip across the city. There were many homeless man who were begging for money. The city can be encoded by an array $$$A$$$ of $$$N$$$ elements , each element being a different place. If the value at $$$A_i$$$ is positive ( including 0 ) , it means that you can steal withdraw $$$A_i$$$ dollars. If it is negative then there is some homeless man begging for $$$|A_i|$$$ dollars. As you are a generous man , you will help exactly $$$K$$$ homeless men. You will visit the $$$N$$$ places in order.Knowing that you initially have 0 dollars and can help a homeless man if and only if you have enough money when you visit him , which is the maximum amount of money you can have after helping $$$K$$$ homeless men of your choosing.

The input consists of integers $$$N,K$$$ , followed by vector $$$A$$$ of $$$N$$$ elements , describing each place in the city.

Print one number - The maximum amount of money you can have after helping $$$K$$$ homeless men. Print -1 if you cannot help $$$K$$$ homeless men.

• $$$N,K \le 10^5$$$ , $$$-10^9 \le A_i \le 10^9$$$
• For 30 points , $$$N,K \le 1000$$$
• For the other 70 points , there are no further restrictions

5 2
1 -3 100 -50 -51

0

Initially we have 0 dollars. We need to help 2 homeless men. We cannot help the one begging for 3 dollars , since we can have at most 1 dollar when we visit him. Instead we will be able to help the last 2 homeless men , since they beg for $$$|-51|+|-50| = 101$$$ dollars , which is the exact amount of money we have when we visit them.