Một trung tâm điều phối đang theo dõi một chiến dịch kéo dài ~n~ ngày. Ở ngày thứ ~i~, mức độ rủi ro dự báo là ~a_i~. Trung tâm muốn chia toàn bộ chiến dịch thành đúng ~k~ giai đoạn giám sát liên tiếp. Mỗi ngày phải thuộc đúng một giai đoạn và các giai đoạn không được chồng lấn lên nhau.

Nếu một giai đoạn bao phủ các ngày từ ~l~ đến ~r~, trung tâm phải chuẩn bị nhân lực và thiết bị theo ngày xấu nhất trong giai đoạn đó, nên chi phí của giai đoạn bằng ~\max(a_l, a_{l+1}, \dots, a_r)~.

Yêu cầu: Hãy lập một kế hoạch giám sát sao cho tổng chi phí của tất cả các giai đoạn là nhỏ nhất.

Input

• Dòng đầu chứa hai số nguyên ~n, k~ ~(1 \le k \le n \le 4000)~.

• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le 10^9)~.

Output

• Một số nguyên là tổng chi phí nhỏ nhất.

Scoring

Sample Input 1

5 2
3 1 4 1 5

Sample Output 1

8

Notes

• Một phương án tối ưu là chia chiến dịch thành hai giai đoạn ~[1, 2]~ và ~[3, 5]~.

• Chi phí lần lượt là ~\max(3, 1) = 3~ và ~\max(4, 1, 5) = 5~, nên tổng chi phí tối thiểu bằng ~8~.