Mot cong ty co \(N\) van phong tai toa do \(x_1 < x_2 < \dots < x_N\). Hang thang, cong ty gui \(K\) dot thu den cac van phong. Moi dot thu phuc vu mot doan van phong lien tiep. Chi phi mot dot gui thu cho doan \([l,r]\) la tong khoang cach tu van phong trung tam (chon toi uu trong doan) den tat ca van phong trong doan. Cu the, chon \(pos\) sao cho \(\sum_{i=l}^r |x_i - pos|\) nho nhat (tuc chon trung vi). Tim tong chi phi nho nhat de gui thu den tat ca van phong.\ \ 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 chi phi nho nhat.\ \ Vi du: Input:

5 2
1 4 7 10 13

Output:

9

Giai thich: \([1,4,7]\) trung vi 4: \(|1-4|+|4-4|+|7-4|=6\); \([10,13]\) trung vi 10: \(|10-10|+|13-10|=3\). Tong = 9.

#

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

Output:

3

Giải thích: Đợt 1 phục vụ [1, 2] tại x=1.5 (chi phí 1), đợt 2 phục vụ [5, 7, 8] tại x=7 (chi phí 2). Tổng = 3.

Ràng buộc & Subtasks