Tý cần giải bài toán sau:

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 đầu chứa số nguyên \(N\) và \(Q\) (\(N, Q \le 10^5\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả một cạnh.

Định dạng đầu ra

• In ra kết quả của từng truy vấn trên một dòng.

Ví dụ

Input:

5 3
1 2
1 3
2 4
2 5
2 3

Output:

3

Ràng buộc