Mot khu cong nghiep hinh chu nhat dai, cac cua hang nam tai toa do \(y_1 < y_2 < \dots < y_N\). Ban can xay \(K\) nha may de phuc vu cac cua hang. Moi cua hang se den nha may gan nhat (khoang cach la chenh lech toa do). Chi phi xay dung mot nha may tai \(p\) de phuc vu cac cua hang trong doan \([l,r]\) la tong binh phuong khoang cach: \(\sum_{i=l}^{r} (y_i - p)^2\). Voi mot doan, vi tri toi uu la trung binh cong cac toa do, chi phi toi thieu co the tinh qua prefix sum. Tim tong chi phi nho nhat khi xay \(K\) nha may (moi nha may phuc vu mot doan lien tiep).\ \ 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.\ \ Vi du: Input:

4 2
1 3 6 10

Output:

9

Giai thich: Nha may 1 phuc vu \([1,2]\) tai 2, chi phi \((1-2)^2+(3-2)^2=2\). Nha may 2 phuc vu \([3,4]\) tai 8, chi phi \((6-8)^2+(10-8)^2=8\). Tong = 10. Phuong an toi uu cho ket qua 9.

#

Đị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 khoảng cách bình phương nhỏ nhất (làm tròn đến số nguyên gần nhất).

Ví dụ

Input:

4 2
1 2 5 6

Output:

1

Giải thích: Nhà máy 1 phục vụ [1, 2] (tâm 1.5, chi phí 0.5), nhà máy 2 phục vụ [5, 6] (tâm 5.5, chi phí 0.5). Tổng = 1.

Ràng buộc & Subtasks