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

Tren truc so co \(N\) ngoi lang tai toa do \(x_1 < x_2 < ... < 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 đầ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