Tim has discovered a time machine! Tim has read enough about time travel to know that he should not do any wacky things, so he decides to be boring and serious: he will get future stock prices using the machine, then trade the stock using that information. However, he needs to be careful: if he makes more than ~K~ trades in a day or has more than one active trade at a time, then he is at risk of impacting the future or being found out.

As Tim's co-founder, you're in charge of figuring out how you can maximize the profits using this knowledge (while Tim takes journeys through time). Given a series of ~N~ future prices that Tim obtained which occur on the same day, can you figure out the most money that you can make using at most ~K~ disjoint, single-stock trades? A trade consists of buying a stock at one point in time, then selling it at a future point in time.

Input Specification

The input begins with two integers ~N, K~ ~(1 \le N \le 10^6, 1 \le K \le 10^3)~, the number of stock prices that Tim obtained and the maximum number of trades ~K~.
The next line contains ~N~ integers ~P_i~ ~(1 \le P_i \le 10^9)~, the future stock prices.

For at least 30 points, ~N, K \le 10^3~.
For at least 60 points, ~N \le 10^4~.
For at least 80 points, ~N \le 10^5~.

Output Specification

Output a single integer, the maximum profit that can be made using at most ~K~ disjoint stock trades.

Sample Input 1

6 2
2 3 1 3 2 5

Sample Output 1

5

Sample Input 2

3 1
3 2 1

Sample Output 2

0