Tren truc so co \(N\) ngoi lang tai toa do \(x_1 < x_2 < \dots < x_N\). Ban can xay \(K\) buu dien sao cho moi lang den buu dien gan nhat co tong khoang cach nho nhat. Khoang cach tu lang \(i\) den buu dien tai p la \(|x_i - p|\). Moi lang se den buu dien gan no nhat (trong doan \([l,r]\) thi dat o trung vi).\ \ Input:

• Dong dau: \(N\), K (\(1 \le K \le N \le 10^4, K \le 1000\))
• Dong sau: \(x_1..x_N\) (\(0 \le x_i \le 10^6\))

Output: Tong khoang cach nho nhat.\ \ Vi du: Input:

6 2
1 2 3 6 8 12

Output:

5

Giai thich: Dat buu dien tai \(2\) va 8, lang 1-3 den 2 (tong 2), lang 4-6 den 8 (tong \(6\)), tong = 8. Phuong an toi uu cho ket qua 5.

#

Định dạng đầu vào

• Dòng 1: Hai số nguyên \(N\) và K (\(1 \le K \le N \le 3000\)).
• Dòng 2: \(N\) số nguyên tăng dần \(x_1, x_2, \dots, x_N\) (\(1 \le x_i \le 10^9\)).

Định dạng đầu ra

• In ra tổng khoảng cách nhỏ nhất.

Ví dụ

Input:

5 2
1 2 3 6 7

Output:

2

Giải thích: Bưu điện 1 đặt tại 2 (\(chi phí 1+0+1=2\)), bưu điện 2 đặt tại 6.5 (\(chi phí 0+0=0\)). Tổng khoảng cách = 2.

Ràng buộc & Subtasks