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

Co \(N\) so nguyen \(a_1, a_2, ..., a_N\). Ban can chia day thanh dung \(K\) doan lien tiep. Moi doan \([l, r]\) co chi phi bang \((a_l + ... + a_r)^2\). Tong chi phi la tong chi phi cac doan. Hay tim cach chia sao cho tong chi phi nho nhat.\ \ Input:

• Dong dau: \(N\) va \(K\) (\(1 \le K \le N \le 10^5\), \(K \le 200\))
• Dong sau: \(a_1..a_N\) (\(|a_i| \le 10^3\))

Output: Mot so nguyen la tong chi phi nho nhat.\ \ Vi du: Input:

5 2
1 3 2 4 1

Output:

36

Giai thich: Chia \([1,3]\) va \([4,5]\), chi phi \((1+3+2)^2 + (4+1)^2 = 36 + 25 = 61\). Phuong an toi uu la \(36\).

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