Co \(N\) nguoi xep hang, nguoi i co chieu cao \(h_i\) (da sap xep tang dan). Ban co \(K\) chiec non, moi non phat cho mot nhom nguoi dung lien tiep trong hang. Chi phi cua mot nhom la chenh lech giua nguoi cao nhat va thap nhat trong nhom (max - min). Tim tong chi phi nho nhat khi chia \(N\) nguoi thanh \(K\) nhom lien tiep.\ \ Input:

• Dong dau: \(N\), K (\(1 \le K \le N \le 10^5, K \le 200\))
• Dong sau: \(h_1..h_N\) (\(0 \le h_i \le 10^9\)) da sap tang dan

Output: Tong chi phi nho nhat.\ \ Vi du: Input:

7 3
1 3 5 8 12 15 20

Output:

13

Giai thich: Chia \([1,3]\) (\(max-min=5-1=4\)), \([4,5]\) (\(12-8=4\)), \([6,7]\) (\(20-15=5\)), tong=13. Phuong an toi uu la 13.

#

Định dạng đầu vào

• Dòng 1: Hai số nguyên \(N\) và K (\(1 \le K \le N \le 3000\)).
• Dòng 2: \(N\) số nguyên tăng dần \(h_1, h_2, \dots, h_N\) (\(1 \le h_i \le 10^9\)).

Định dạng đầu ra

• In ra tổng chênh lệch chiều cao nhỏ nhất.

Ví dụ

Input:

5 2
1 3 4 8 9

Output:

4

Giải thích: Nhóm 1 gồm [1, 3, 4] (\(chênh lệch 4 -1 = 3\)), nhóm 2 gồm [8, 9] (\(chênh lệch 9 -8 = 1\)). Tổng = 4.

Ràng buộc & Subtasks