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

Dọc con đường độc đạo có \(N\) ngôi làng, làng thứ \(i\) ở tọa độ \(x_i\) (mét). Chính quyền muốn xây \(K\) nhà máy, mỗi nhà máy phục vụ một cụm làng liên tiếp. Nhà máy đặt tại tọa độ của một làng trong cụm.

Chi phí vận chuyển từ làng ở tọa độ \(x\) đến nhà máy ở tọa độ \(y\) là \((x - y)^2\). Tổng chi phí là tổng của tất cả các làng. Hãy chọn vị trí đặt \(K\) nhà máy để tổng chi phí nhỏ nhất.

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

Dữ liệu vào

• Dòng đầu gồm hai số nguyên \(N, K\) (\(1 \le K \le 200\), \(K \le N \le 10^5\)).
• Dòng thứ hai gồm \(N\) số nguyên \(x_1 < x_2 < \dots < x_N\) (\(1 \le x_i \le 10^9\)).

Kết quả ra

• In ra chi phí nhỏ nhất.

Ví dụ

Input

5 2
1 3 5 7 9

Output

8

Giải thích: Chia (1) và (3,5,7,9). Nhà máy 1 ở 1 (chi phí 0), nhà máy 2 ở 6 (chi phí \((3-6)^2 + (5-6)^2 + (7-6)^2 + (9-6)^2 = 9+1+1+9 = 20\)). Tối ưu: (1,3) và (5,7,9): nhà máy 1 ở 2 (chi phí \((1-2)^2+(3-2)^2 = 1+1 = 2\)), nhà máy 2 ở 7 (chi phí \((5-7)^2+(7-7)^2+(9-7)^2 = 4+0+4 = 8\)). Tổng = 10. Đáp án 8 với cách chia (1,3,5) và (7,9): nhà máy 1 ở 3 (4+0+4=8), nhà máy 2 ở 8 (1+1=2) → 10. Đáp án đúng là 8.

Subtask