Mot con duong dai \(L\) met, co N dia diem dep tai vi tri \(p_1 < p_2 < \dots < p_N\). Ban muon xay \(K\) tram dung chan (moi tram phuc vu mot doan duong lien tiep). Voi doan \([l,r]\), du khach se di tu dau den cuoi doan, chi phi la binh phuong khoang cach giua diem dau va diem cuoi cua doan: \((p_r - p_l)^2\). Tim tong chi phi nho nhat.\ \ Input:

• Dong dau: \(N\), K (\(1 \le K \le N \le 10^5, K \le 200\))
• Dong sau: \(p_1..p_N\) (\(0 \le p_i \le 10^9\))

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

5 2
0 3 7 10 15

Output:

41

Giai thich: Chia \([0,3,7]\) (\((7-0)^2=49\)) va \([10,15]\) (\((15-10)^2=25\)), tong=74. Phuong an toi uu cho ket qua 41.

#

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

• Dòng 1: Ba số nguyên \(L, N, K\) (\(1 \le K \le N \le 3000, 1 \le L \le 10^9\)).
• Dòng 2: \(N\) số nguyên tăng dần \(p_1, p_2, \dots, p_N\) (\(1 \le p_i \le L\)).

Định dạng đầu ra

• In ra tổng bình phương khoảng cách nhỏ nhất.

Ví dụ

Input:

10 4 2
1 3 7 9

Output:

8

Giải thích: Trạm 1 cho [1, 3] (\(chi phí (3-1)^2 = 4\)), trạm 2 cho [7, 9] (\(chi phí (9-7)^2 = 4\)). Tổng = 8.

Ràng buộc & Subtasks