Robot

Một dây chuyền xuất khẩu cam của công ty XYZ tiến hành đánh giá sản phẩm. Trên dây chuyền có $n$ quả cam đánh số từ $1$ đến $n$ đang được đưa vào đánh giá chất lượng, quả thứ $i$ có hàm lượng độc tố là $a_i$ $(i=1,2,\dots ,n)$. Rô bốt P của công ty thực hiện việc phân lô sản phẩm để chia $n$ quả cam trên thành đúng $k$ lô. Cam được phân lô theo thứ tự từ đầu đến cuối, mỗi lô ít nhất một quả (mỗi lô là một đoạn các quả cam liên tiếp). Rô bốt Q của công ty đối tác thực hiện việc đánh giá chất lượng, với mỗi lô cam, rô bốt Q sẽ chọn ra một quả có hàm lượng độc tố lớn nhất để làm đại diện cho lô hàng đó. Hàm lượng độc tố của một lô là hàm lượng độc tố của quả đại diện.

Yêu cầu: Hãy lập trình giúp rô bốt P chia lô sao cho tổng hàm lượng độc tố của tất cả $k$ lô cam là nhỏ nhất có thể.

Dữ liệu vào

• Dòng thứ nhất gồm hai số nguyên dương $n,k$ $(k\le n)$;
• Dòng thứ hai gồm $n$ số nguyên dương $a_1,a_2,\dots ,a_n$ $(a_i\le {10}^9;1\le i\le n)$.

Các số ghi trên cùng một dòng được phân cách nhau bởi một dấu cách.

Dữ liệu ra

Một số nguyên là tổng hàm lượng độc tố nhỏ nhất tìm được.

Ràng buộc

• $1\le k\le n\le 2·{10}^5$, $1\le a_i\le {10}^9$.
• Nếu dãy $a$ không phải dãy không giảm thì $n\le 5·{10}^4$ (đề gốc là $n\le 2·{10}^5$ cho mọi test; trên CTOJ giới hạn này được giảm ở subtask 4).

Subtasks

• Subtask 1 ($30\%$ số điểm): $n\le 100$.
• Subtask 2 ($30\%$ số điểm): $n\le 1000$.
• Subtask 3 ($20\%$ số điểm): $a_i\le a_{i+1}$ $(1\le i<n)$, $n\le 2·{10}^5$.
• Subtask 4 ($20\%$ số điểm): $n\le 5·{10}^4$, không có giới hạn gì thêm.

Ví dụ