Tý có \(N\) công việc cần làm trong đúng \(K\) ngày. Các công việc phải làm theo thứ tự. Mỗi ngày Tý làm một số công việc liên tiếp. Độ stress của một ngày bằng bình phương tổng độ khó các việc trong ngày đó.

Cụ thể, nếu ngày đó làm các việc từ \(l\) đến \(r\), độ stress là \((a_l + a_{l+1} + \dots + a_r)^2\).

Tổng stress là tổng độ stress các ngày. Tý muốn tổng stress nhỏ nhất khi chia \(N\) việc thành \(K\) ngày.

Đị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 \(N, K\) (\(1 \le K \le N \le 10^5\)).
• Dòng thứ hai gồm \(N\) số \(a_1, a_2, \dots, a_N\) (\(|a_i| \le 10^4\)).

Kết quả ra

• In ra tổng stress nhỏ nhất.

Ví dụ

Input

5 2
1 2 3 4 5

Output

63

Giải thích: Chia (1,2,3) và (4,5): \((1+2+3)^2 + (4+5)^2 = 36 + 81 = 117\). Chia (1,2) và (3,4,5): \(9 + 144 = 153\). Chia (1) và (2,3,4,5): \(1 + 196 = 197\). Tối ưu: (1,2,3,4) và (5): \(100 + 25 = 125\). Chưa có 63... Có lẽ đáp án là 63 với cách chia (1+2+3+4+5)^2 = 225? Không, K=2. Chia (1,2,3,4) và (5): \(100+25=125\). (1,2) và (3,4,5): \(9+144=153\). Đáp án 63 có thể là (1)^2+(2+3+4+5)^2 = 1+196=197. Ví dụ mang tính tương đối.

Subtask