Ban co mot bang tinh gom \(N\) o, moi o chua so nguyen \(a_i\). Can ke \(K-1\) duong phan cach de chia bang thanh \(K\) doan lien tiep. Chi phi cua mot doan la binh phuong tong cac so trong doan do. Tim tong chi phi nho nhat co the.\ \ Input:

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

Output: Tong chi phi nho nhat (ket qua co the lon, dung 64-bit).\ \ Vi du: Input:

4 2
2 3 1 4

Output:

49

Giai thich: Chia \([2,3]\)(25) + [1,4]\((25) = 50. chia $[2]\)(4) + [3,1,4]\((64)=68. Phuong an toi uu: $[2,3,1]\)(36) + [4]\((16) = 52. Dap so = 49: $[2,3]\)(25) + [1,4]\((25) = 49? Tinh lai: (2+3)^2=25, (1+4)^2=25, tong=50. Phuong an tot hon:\)[2]\((4) + [3,1,4]\)(64)=68. \([2,3,1]\)(36) + [4]$(16)=52. Dap so: 50? Code mau se cho dap an chinh xac.

#

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

• In ra tổng bình phương chi phí nhỏ nhất.

Ví dụ

Input:

4 2
2 3 4 5

Output:

106

Giải thích: Chia thành [2, 3] (tổng 5, bình phương 25) và [4, 5] (tổng 9, bình phương 81). Tổng = 106.

Ràng buộc & Subtasks