Tý có một phi hành gia cần sắp xếp \(N\) vật phẩm vào các thùng chứa để mang lên tàu vũ trụ. Các vật phẩm được đặt trên một băng chuyền theo thứ tự \(a_1, a_2, \dots, a_N\).

Mỗi thùng chứa có thể chứa một đoạn các vật phẩm liên tiếp. Chi phí để đóng gói một thùng chứa các vật phẩm từ \(j+1\) đến \(i\) là: \[\left( \sum_{k=j+1}^{i} a_k \right)^2\]

Phi hành gia muốn chia tất cả \(N\) vật phẩm vào đúng \(K\) thùng chứa sao cho tổng chi phí là nhỏ nhất.

Hãy tính tổng chi phí nhỏ nhất đó.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(N\) (\(1 \le N \le 10^5\)) và \(K\) (\(1 \le K \le N\)).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^3\)).

Định dạng đầu ra

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

Ví dụ

Input:

6 3
1 3 2 4 1 2

Output:

29

Giải thích: Chia \([1], [3,2,4], [1,2]\): \(1^2 + (3+2+4)^2 + (1+2)^2 = 1+81+9=91\). Tối ưu: \([1,3], [2,4], [1,2]\): \(16+36+9=61\).

Ràng buộc

• Subtask 1 (30%): \(N \le 2000\).
• Subtask 2 (30%): \(K \le 100, N \le 10^5\).
• Subtask 3 (40%): \(N \le 10^5\).