Trong quá trình khảo cổ, nhà nghiên cứu Henry đã phát hiện một chuỗi gồm ~N~ hạt ngọc được xâu lại thành một vòng tròn khép kín. Henry đã đánh số các viên ngọc liên tiếp từ ~1~ đến ~N~, viên ngọc thứ ~i~ ~(1 \le i < N)~ nằm liền kề với viên ngọc thứ ~i + 1~, viên ngọc thứ ~N~ nằm liền kề với viên ngọc thứ ~1~. Viên ngọc thứ ~i~ mang giá trị là một số nguyên dương ~A_i~.

Để phục vụ cho quá trình nghiên cứu, Henry bắt buộc phải tách chuỗi ngọc này thành ~K~ đoạn liên tiếp nhau để phân tích. Chi phí để tách một đoạn liên tiếp các chuỗi ngọc được tính bằng bình phương tổng giá trị các viên ngọc nằm trong đoạn đó.

Cụ thể, nếu một đoạn ngọc có ~m~ viên ngọc với giá trị các viên ngọc lần lượt là ~A_1, A_2, A_3, \dots, A_m~, chi phí để tách đoạn này là: ~(A_1 + A_2 + \dots + A_m)^2~.

Tổng chi phí của quá trình tách thành ~K~ đoạn chính là tổng chi phí của ~K~ đoạn ngọc được tạo thành. Nhiệm vụ của Henry là tìm cách cắt chuỗi ngọc sao cho tổng chi phí để cắt là nhỏ nhất.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~N, K~ ~(2 \le K \le N \le 1000)~ — ~N~ là số lượng viên ngọc của chuỗi ngọc, ~K~ là số đoạn ngọc cần tách.

• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, A_3, \dots, A_N~ ~(1 \le A_i \le 10^5)~ — giá trị của các viên ngọc.

Output

Một số nguyên duy nhất là tổng chi phí nhỏ nhất để chia chuỗi ngọc thành ~K~ đoạn.

Scoring

Sample Input 1

6 2
2 6 5 2 1 4

Sample Output 1

202

Notes

Chia chuỗi ngọc với thứ tự các chỉ số như sau:

• Chuỗi ngọc 1: ~(2, 3)~.

• Chuỗi ngọc 2: ~(4, 5, 6, 1)~.

• Tổng chi phí: ~(6 + 5)^2 + (2 + 1 + 4 + 2)^2 = 202~.