Mua bán cỏ

Sau cuộc phiêu lưu cùng nhau, Dế Mèn và Dế Trũi lên kế hoạch trở về quê nhà. Hành trình trở về quê của hai bạn sẽ đi qua \(N\) thành phố, các thành phố lần lượt được đánh số từ \(1\) đến \(N\). Giá bán một xe cỏ tại thành phố thứ \(i\) (\(1 \le i \le N\)) là \(A_i\) (\(1 \le A_i \le 10^9\)). Nếu mua một xe cỏ ở thành phố \(i\) và mang đến bán ở thành phố \(j\) thì thu được lợi nhuận là \(A_j - A_i\) (\(1 \le i < j \le N\)).

Vì giao thông không thuận lợi nên trên đường đi hai bạn chỉ mang theo được tối đa một xe cỏ. Để đảm bảo thời gian di chuyển nên số lần mua và bán một xe cỏ không được vượt quá \(K\) lần.

Yêu cầu:
Hãy lập trình tính tổng lợi nhuận tối đa mà hai bạn có thể thu được trên hành trình trở về quê nhà.

Input

• Dòng đầu ghi hai số nguyên dương lần lượt \(N, K\) (\(K \le N \le 200000\)).
• Dòng thứ hai ghi lần lượt \(N\) số nguyên dương \(A_1, A_2, \ldots, A_N\).
• Các số trong tệp cách nhau ít nhất một dấu cách.

Output

• Ghi ra một số nguyên duy nhất là tổng lợi nhuận tối đa có thể thu được.

Example

5 1
4 1 3 5 6

5

5 2
1 4 2 5 6

7

Scoring

• Có 20% số điểm tương ứng với \(K = 1\);
• Có 30% số điểm tương ứng với \(K = 2\);
• Có 30% số điểm tương ứng với \(3 \le K \le 100\);
• Có 20% số điểm tương ứng với \(100 < K, N \le 200000\).