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

Mot cong ty co \(N\) van phong tai toa do \(x_1 < x_2 < ... < 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 đầ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