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

Tren mot duong thang co \(2N\) thiet bi tai toa do \(x_1 < x_2 < ... < x_{2N}\). Ban can ghep chung thanh \(N\) cap, moi cap gom hai thiet bi lien ke nhau (sau khi ghep, cac cap tao thanh mot phan hoach cua day). Chi phi noi day cho cap \((l,r)\) la \((x_r - x_l)^2\). Do gioi han ky thuat, ban chi co the noi toi da \(K\) soi cap (tuc \(K\) cap). Nhu vay \(2N\) thiet bi duoc chia thanh \(K\) nhom, moi nhom la mot doan lien tiep gom so chan thiet bi. Tim tong chi phi nho nhat de noi tat ca thiet bi.\ \ Input:

• Dong dau: \(N\), \(K\) (\(1 \le K \le N \le 10^5\), \(K \le 200\))
• Dong sau: \(x_1..x_{2N}\) (\(0 \le x_i \le 10^9\))

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

3 2
1 4 6 9 11 14

Output:

18

Giai thich: Chia \([1,4,6,9]\) (ghep (1,4):9, (6,9):9 = 18) va \([11,14]\) (9) = 27. Phuong an toi uu cho ket qua 18.

Đị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