Cho mảng ~a~ gồm ~n~ phần tử và một số nguyên ~k~. Tách mảng ~a~ ra thành ~k~ đoạn liên tiếp sao cho mỗi phần tử của mảng ~a~ thuộc đúng một đoạn và không có đoạn nào rỗng. Chi phí của một đoạn liên tiếp là bình phương của tổng các phần tử được chọn, chi phí của cả ~k~ đoạn là chi phí của đoạn lớn nhất. Tìm cách cắt để cực tiểu hóa chi phí.

Input

Dòng đầu tiên gồm hai số nguyên ~n, k~.

Dòng tiếp theo gồm ~n~ số nguyên ~a_1, a_2, \cdots, a_n~.

Output

In ra chi phí cực tiểu.

Scoring

• Subtask ~1~ (chiếm ~20\%~ số điểm): ~1 \leq k \leq n \leq 21~; ~-10^4 \leq a_i \leq 10^4~.

• Subtask ~2~ (chiếm ~30\%~ số điểm): ~1 \leq n \leq 1000~; ~1 \leq k \leq \min(n, 30)~; ~-10^4 \leq a_i \leq 10^4~.

• Subtask ~3~ (chiếm ~50\%~ số điểm): ~1 \leq n \leq 10000~; ~1 \leq k \leq \min(n, 40)~; ~-10^4 \leq a_i \leq 10^4~.

Sample Input 1

7 3
15 20 -4 8 14 -2 -5

Sample Output 1

256

Sample Input 2

7 4
-1 -1 -1 1 -1 -1 -1

Sample Output 2

4