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.

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