Trong lễ hội mùa đông, có N điểm sáng nằm trên một trục thẳng. Tọa độ của chúng lần lượt là x_1, x_2, ..., x_N, với x_1 < x_2 < ... < x_N.

Ban tổ chức muốn chia các điểm sáng thành đúng K nhóm không rỗng. Mỗi nhóm gồm các điểm liên tiếp theo thứ tự tọa độ. Nếu một nhóm gồm các điểm từ l đến r, chi phí của nhóm là bình phương độ dài đoạn từ x_l đến x_r, tính cả hai đầu mút:

Chi phí = (x_r - x_l + 1)^2

Hãy tìm tổng chi phí nhỏ nhất có thể.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên N và K.
• Dòng thứ hai chứa N số nguyên x_1, x_2, ..., x_N theo thứ tự tăng dần.

Dữ liệu ra

In ra một số nguyên là tổng chi phí nhỏ nhất.

Giới hạn

• 1 <= K <= N <= 5000.
• 0 <= x_1 < x_2 < ... < x_N <= 10^6.

Ví dụ

Input

4 2
1 2 3 4

Output

8

Giải thích: Chia thành hai nhóm gồm các điểm [1, 2] và [3, 4]. Mỗi nhóm có độ dài 2, nên tổng chi phí là 2^2 + 2^2 = 8.

Phân nhóm điểm

Mỗi test được chấm độc lập; không áp dụng chấm theo batch.