Tren mot duong thang co \(2N\) thiet bi tai toa do \(x_1 < x_2 < \dots < 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 1: Hai số nguyên \(N\) và K (\(1 \le K \le N \le 2000\)).
• Dòng 2: \(2N\) số nguyên tăng dần \(x_1, x_2, \dots, x_{2N}\) (\(1 \le x_i \le 10^9\)).

Định dạng đầu ra

• Một số nguyên duy nhất là tổng chi phí nhỏ nhất.

Ví dụ

Input:

3 2
1 2 5 7 10 11

Output:

5

Giải thích: Ghép \((1, 2)\) chi phí 1, \((5, 7)\) chi phí 4, \((10, 11)\) chi phí 1. Chia làm 2 nhóm: { \((1, 2)\) }, { \((5, 7)\), \((10, 11)\) }. Tổng chi phí = 1 + 4 = 5.

Ràng buộc & Subtasks