~NH~ đang sở hữu một sợi dây chuyền lấp lánh gồm 𝑛 hạt ngọc trai quý giá. Các hạt ngọc trai được đánh số liên tục từ 1 đến n. Hạt ngọc thứ i có giá trị là một số nguyên dương ~a_i~ và được kết lại tạo thành một vòng khép kín. Điều đặc biệt là chiếc vòng này không có điểm bắt đầu hay kết thúc, hạt thứ ~i (1 ≤ i < 𝑛)~ nằm bên trái hạt thứ ~i + 1~, hạt ngọc thứ n nằm bên trái hạt ngọc thứ 1.

Giờ đây, ~NH~ muốn chia dây chuyền thành 𝑘 đoạn gồm các hạt ngọc liên tiếp nhau. Tuy nhiên, khi cắt phải tốn chi phí rất lớn, để tạo thành một đoạn các hạt ngọc trai liên tiếp sẽ tiêu tốn chi phí bằng bình phương tổng các giá trị của các hạt ngọc trai trong đoạn. Cụ thể hơn, nếu đoạn các hạt ngọc có độ dài là 𝑚 và dãy giá trị là ~𝑏_1, 𝑏_2, … , 𝑏_𝑚~, chi phí cắt của đoạn này bằng ~(𝑏_1 + 𝑏_2 + ⋯ + 𝑏_𝑚)^2~.

Chi phí của một cách cắt tạo thành 𝑘 đoạn ngọc chính là bằng tổng chi phí của các đoạn tạo thành.

Yêu cầu: Tìm cách cắt dây chuyền thành 𝑘 đoạn sao cho tổng chi phí phải trả là nhỏ nhất.

Dữ liệu vào từ file văn bản PEARL.INP gồm có cấu trúc

• Dòng đầu tiên chứa hai số nguyên 𝑛, 𝑘 ~(2 ≤ 𝑘 ≤ 𝑛 ≤ 1000)~ với 𝑛 là số hạt ngọc trai, 𝑘 là số đoạn cần chia.

• Dòng thứ hai chứa 𝑛 số nguyên dương ~a_1, a_2, … , a_n (1 ≤ a_i ≤ 10^5)~ là giá trị của các hạt ngọc.

Kết quả ghi ra tệp văn bản PEARL.OUT có cấu trúc

• Ghi một số nguyên duy nhất là tổng chi phí tối thiểu để chia vòng tay thành 𝑘 đoạn.

Input:

6 2
2 6 5 2 1 4

Output:

202

Giải thích: Cách cắt tối ưu là (6,5), (2,1,4,2) Với tổng chi phí là: ~(6 + 5)^2 + (2 + 1 + 4 + 2)^2~ = 202.

Input:

5 5
austria
autocorrect
program
programming
computer
autocorrelation
programming
competition
zyx
austria 

Output:

12
4
11
3
2