Co \(N\) so nguyen \(a_1, a_2, \dots, a_N\). Ban can chia day thanh dung \(K\) doan lien tiep. Mỗi đoạn \([l, r]\) có chi phí bằng \((a_l + \dots + 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 1: Hai số nguyên \(N\) và K (\(1 \le K \le N \le 3000\)).
• Dòng 2: \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^4\)).

Định dạng đầu ra

• Một số nguyên duy nhất là tổng chi phí nhỏ nhất.

Ví dụ

Input:

5 2
1 2 3 4 5

Output:

117

Giải thích: Chia thành 2 đoạn [1..3] (tổng 6, chi phí 36) và [4..5] (tổng 9, chi phí 81). Tổng = 36 + 81 = 117.

Ràng buộc & Subtasks