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

Mot chuoi cua hang co \(N\) chi nhanh tren truc so chinh, toa do \(y_1 < y_2 < ... < 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 đầ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