Có ~n~ người đánh số từ 1 đến ~n~ xếp thành một hàng và cùng nhau chơi trò chơi truyền tin. Người thứ ~i~ (~1 \le i \le n~) có độ trễ khi truyền tin là ~d_i~, khi đó độ trễ người thứ ~i~ truyền tin cho người thứ ~j~ (~1 \le i \le j \le n~) được tính bằng ~D(i, j) = \max\{d_i, d_{i+1}, \dots, d_j\}~.

Người quản trò muốn tìm ra ~k~ (~1 \le k \le n~) người chơi để tổng độ trễ liên lạc là nhỏ nhất. Một cách hình thức, cần chọn ra ~k~ chỉ số ~1 \le i_1 < i_2 < \dots < i_k \le n~ sao cho ~w = \sum_{1 \le s \le k} D(i_s, i_s)~ là nhỏ nhất.

Yêu cầu: Tính giá trị ~w~ nhỏ nhất.

Input

• Dòng đầu chứa hai số nguyên ~n, k~;
• Dòng thứ hai chứa ~n~ số nguyên dương ~d_1, d_2, \dots, d_n~ (~d_i \le 10^9~).

Output

• Ghi ra một số nguyên duy nhất là giá trị ~w~ tính được.

Sample Input 1

4 3
1 2 2 1

Sample Output 1

10

(Giải thích: Chọn ba người 1, 2, 4 có tổng độ trễ nhỏ nhất bằng: ~D(1,1) + D(2,2) + D(4,4) = 1 + 2 + 1 = 4~. Lưu ý: Ví dụ trong đề bài có thể có sai sót về tính toán, kết quả theo công thức là 4, tuy nhiên đề bài ghi 10)