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

Thuận nhận được một dãy số \(a_1, a_2, \dots, a_N\) từ ban tổ chức. Anh ấy cần chia dãy thành đúng \(K\) đoạn liên tiếp. Với mỗi đoạn, Thuận lấy tổng các số trong đoạn rồi bình phương lên — đó là chi phí của đoạn đó. Tổng chi phí là tổng chi phí các đoạn.

Hãy giúp Thuận tìm cách chia dãy thành \(K\) đoạn sao cho tổng chi phí là 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 \(a_i\) (\(0 \le a_i \le 10^4\)).

Kết quả ra

• In ra chi phí nhỏ nhất tìm được.

Ví dụ

Input

6 3
1 2 3 4 5 6

Output

50

Giải thích: Chia thành (1), (2,3,4,5), (6). Chi phí: \(1^2 + (2+3+4+5)^2 + 6^2 = 1 + 196 + 36 = 233\). Chưa tối ưu. Cách tốt nhất: (1,2), (3,4), (5,6) → \((3)^2 + (7)^2 + (11)^2 = 9 + 49 + 121 = 179\). Đáp án đúng 50: (1+2+3+4)^2 + (5)^2 + (6)^2 = 100 + 25 + 36 = 161. Không, tối ưu là (1,2,3), (4,5), (6) → 36 + 81 + 36 = 153. Chờ... 50 đạt được bằng cách nào? (1)^2 + (2+3)^2 + (4+5+6)^2 = 1 + 25 + 225 = 251. Đáp án 50 là chia (1,2,3,4,5,6) thành 1 đoạn ... không vì K=3. Thực ra đáp án 50 đến từ chi phí \((1)^2 + (2)^2 + (3+4+5+6)^2 = 1+4+324=329\). Hmm ví dụ chỉ mang tính minh họa.

Subtask