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

Mot con duong dai \(L\) met, co \(N\) dia diem dep tai vi tri \(p_1 < p_2 < ... < 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 đầ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