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 \leq i \leq 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 \leq i \leq j \leq n)~ được tính bằng ~D(i, j)=\max \left\{d_{i}, d_{i+1}, \ldots, d_{j}\right\}~.

Người quản trò muốn tìm ra ~k(1 \leq k \leq 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 \leq i_{1} \lt i_{2}\lt \cdots \lt i_{k} \leq n~ sao cho ~w=\sum_{1 \leq x \leq y \leq k} D\left(i_{x}, i_{y}\right)~ là nhỏ nhất.

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

Dữ liệu:

• 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}, \ldots, d_{n}\left(d_{i} \leq 10^{9}\right)~.

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

Ràng buộc:

• Có ~20 \%~ số test ứng với ~20 \%~ số điểm của bài thỏa mãn: ~n \leq 20~;
• 30\% số test khác ứng với ~30 \%~ số điểm của bài thỏa mãn: ~k=3~ và ~n \leq 10^{4}~;
• 30\% số test khác ứng với ~30 \%~ số điểm của bài thỏa mãn: ~n \leq 500~;
• ~20 \%~ số test còn lại ứng với ~20 \%~ số điểm của bài thỏa mãn: ~n \leq 10^{4}~.

Ví dụ:

Sample Input

4 3  
1 2 2 1

Sample Output

10

Giải thích:

Chọn ba người ~1,2,4~ có tổng độ trễ nhỏ nhất bằng: ~D(1,2)+D(1,4)+D(2,4)+D(1,1)+D(2,2)+D(4,4)=10~.