METOXES

A stock exchange company wants to evaluate a trading practice known as the ~K~-hits strategy.

We are given the prices ~p_1~, ~p_2~, ~...~, ~p_N~ of a stock for a period of ~N~ days. The company intends to buy and sell this stock at most ~M~ times during this period. Let's assume that there will be ~K \le M~ transactions, and in the ~i~-th transaction, the company will buy the stock on day ~b_i~ and sell it on day ~s_i~. The time intervals [~b_i~, ~s_i~] do not overlap, meaning: ~1 \le b_1 < s_1 < b_2 < s_2 < ... < b_K < s_K \le N~. The total profit ~X~ of the company from all transactions is obviously:

$$\displaystyle X = \sum_{i=1}^K \left(p_{s_i}-p_{b_i}\right)$$

The company wants to find out how many transactions it should make and when, in order to maximize the profit ~X~. In other words, it wants to determine the value of ~K~ and the boundaries of the intervals [~b_i~, ~s_i~].

Input

The first line of input will contain two natural numbers ~N~ and ~M~: the number of days and the maximum number of transactions. The second line of input will contain ~N~ integers ~p_i~, separated in pairs by a single space: the stock prices.

Output

The output should consist of a single line containing exactly one natural number: the maximum profit ~X~ that can be achieved with at most ~M~ transactions.

Constraints

~1 \le N \le 100.000~
~0 \le M \le 1.000~
~1 \le p_i \le 10.000~
Execution time limit: 1 sec.
Memory limit: 64 MB.

Examples of Input - Output Files:

1st

STDIN (metoxes.in)

10 3
12 12 7 10 15 8 3 4 8 8

STDOUT (metoxes.out)

13

Explanation of first example: In the first example, the company can achieve the maximum profit by making only ~2~ transactions:

• Buying on the ~3~rd day at the price of ~7~ and selling on the ~5~th day at the price of ~15~.
• Buying on the ~7~th day at the price of ~3~ and selling on the ~9~th day (or the ~10~th day) at the price of ~8~.

Thus, its profit is ~(15-7) + (8-3) = 13~. This is the maximum possible.

2nd

STDIN (metoxes.in)

5 2
10 9 8 7 6

STDOUT (metoxes.out)

0

Explanation of the second example: In the second example, the stock price decreases every day, so the maximum possible profit is zero if no transactions are made.