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

Mot khu cong nghiep hinh chu nhat dai, cac cua hang nam tai toa do \(y_1 < y_2 < ... < 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 đầ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