DreamGrid's Bookshop Mystery

DreamGrid visited a bookshop that contains \(n\) books with prices \(a_1, a_2, \dots, a_n\). Being very rich, he bought the books according to the following strategy:

• Check the books from the 1^st to the \(n\)th one in order.
• If at the moment of checking a book his current money is at least the price \(a_i\) of the book, he buys it and his money is reduced by \(a_i\).
• If his money is less than \(a_i\) then he skips that book.

It is observed that DreamGrid ended up buying exactly \(m\) books. BaoBao is curious about how rich DreamGrid is. You are asked to determine the maximum possible initial amount of money (a non-negative integer) that DreamGrid could have had so that following the above strategy he ended up buying exactly \(m\) books.

Note: The decision process is greedy. In particular, once DreamGrid has enough money for a book \(a_i\), he must buy it, which reduces his money. Therefore, if he had too much money, he might end up buying more than \(m\) books. Your task is to find the maximum possible \(P\) (initial money) for which the greedy simulation results in exactly \(m\) purchases.

inputFormat

The first line contains two integers \(n\) and \(m\) (where \(1 \le n \le 10^5\) and \(0 \le m \le n\)).

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) representing the prices of the books.

outputFormat

Output a single non-negative integer: the maximum possible initial money DreamGrid could have had such that he buys exactly \(m\) books following the strategy described.

sample

2 1
3 2

4