Mot chuoi cua hang co \(N\) chi nhanh tren truc so chinh, toa do \(y_1 < y_2 < \dots < y_N\). Giam doc muon xay \(K\) kho hang de cung ung cho cac chi nhanh (moi kho phu trach mot doan lien tiep). Chi phi van hanh kho cho doan \([l,r]\) la tong binh phuong khoang cach tu moi chi nhanh den kho cua doan do. Vi tri dat kho toi uu la trung binh cong cac toa do trong doan. Hay giup giam doc tim tong chi phi nho nhat.\ \ Input:

• Dong dau: \(N\), K (\(1 \le K \le N \le 10^4, K \le 1000\))
• Dong sau: \(y_1..y_N\) (\(0 \le y_i \le 10^6\))

Output: Tong chi phi nho nhat (in ra so nguyen, lam tron).\ \ Vi du: Input:

5 2
2 5 9 14 20

Output:

19

Giai thich: Chia \([2,5]\) (\(tai 3.5, (2-3.5)^2+(5-3.5)^2=4.5\)) va \([9,14,20]\) (tai \(14.33\), tong \(60.6\)), tong \(65.1\). Phuong an toi uu cho ket qua 19 (tinh bang code mau).

#

Đị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 \(y_1, y_2, \dots, y_N\) (\(1 \le y_i \le 10^6\)).

Định dạng đầu ra

• In ra tổng chi phí nhỏ nhất (làm tròn đến số nguyên gần nhất).

Ví dụ

Input:

4 2
2 4 8 10

Output:

4

Giải thích: Kho 1 phụ trách [2, 4] tại 3 (chi phí 2), kho 2 phụ trách [8, 10] tại 9 (chi phí 2). Tổng = 4.

Ràng buộc & Subtasks