Vòng ngọc cổ

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, \ldots, A_m\), chi phí để tách đoạn này là: \((A_1 + A_2 + \ldots + 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ữ liệu vào có cấu trúc:

• 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, \ldots, A_N\) (\(1 \le A_i \le 10^5\)) --- giá trị của các viên ngọc.

Ràng buộc:

• Có \(20\%\) số điểm tương ứng với \(K = 2\), \(2 \le N \le 10^3\).

• Có \(20\%\) số điểm tương ứng với \(2 \le K \le N \le 20\).

• Có \(20\%\) số điểm tương ứng với \(2 \le K \le N \le 100\).

• Có \(20\%\) số điểm tương ứng với \(2 \le K \le N \le 250\).

• Có \(20\%\) số điểm tương ứng với \(2 \le K \le N \le 500\).

Output

In ra 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.

Example

Input:

6 2
2 6 5 2 1 4

Output:

202

Note

Chia chuỗi ngọc (xếp thành vòng tròn) thành \(2\) đoạn: đoạn thứ nhất gồm các viên ngọc \((2, 3)\), đoạn thứ hai gồm các viên ngọc \((4, 5, 6, 1)\). Tổng chi phí: \((6+5)^2 + (2+1+4+2)^2 = 121 + 81 = 202\).