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 ~k~ lô. Cam được phân lô theo thứ tự từ đầu đến cuối, mỗi lô ít nhất một quả. 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 đó.

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

Input

• Dòng thứ nhất gồm hai số nguyên dương ~n, k~ ~(k \le n \le 2 \cdot 10^5)~;

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

Output

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

Scoring

Sample Input 1

7 3
2 5 1 8 9 2 6

Sample Output 1

15

Notes

Các lô cam thỏa mãn:

• Lô 1: ~2, 5~;

• Lô 2: ~1~;

• Lô 3: ~8, 9, 2, 6~.