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 đi qua đượ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ỏ (phải bán xe cỏ đang mang rồi mới được mua xe tiếp theo). Để đả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, tức là có nhiều nhất $K$ lượt, mỗi lượt gồm mua một xe cỏ ở một thành phố rồi bán nó ở một thành phố phía sau. Hai bạn có thể không mua bán lần nào (lợi nhuận bằng $0$).

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à.

Dữ liệu vào

• 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,\dots ,A_N$.

Các số cách nhau ít nhất một dấu cách.

Dữ liệu ra

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

Ràng buộc

• $1\le K\le N\le 200000$
• $1\le A_i\le {10}^9$

Subtasks

• Subtask 1 ($20\%$ số điểm): $K=1$.
• Subtask 2 ($30\%$ số điểm): $K=2$.
• Subtask 3 ($30\%$ số điểm): $3\le K\le 100$.
• Subtask 4 ($20\%$ số điểm): $100<K\le N\le 200000$.

Ví dụ