Phân chia kho báu

Trong một vương quốc nọ, có một bộ sưu tập đá quý vô giá được cất giữ trong một chiếc rương lớn. Bộ sưu tập này bao gồm \(n\) viên đá quý được sắp xếp thành một hàng, mỗi viên đá thứ \(i\) có giá trị là \(x_i\). Vị vua của vương quốc muốn chia bộ sưu tập này thành \(k\) phần để cất giữ ở \(k\) kho báu khác nhau.

Việc phân chia phải tuân theo một quy tắc nghiêm ngặt: các viên đá quý phải được chia thành các đoạn liên tiếp, và mỗi kho báu sẽ chứa đúng một đoạn. Chi phí để cất giữ mỗi đoạn đá quý được tính bằng bình phương của tổng giá trị các viên đá trong đoạn đó. Vua muốn tìm cách phân chia sao cho tổng chi phí của tất cả \(k\) kho báu là nhỏ nhất có thể.

Bạn là một vị quân sư tài ba, được giao nhiệm vụ tìm ra cách phân chia tối ưu này để giúp nhà vua tiết kiệm chi phí.

Input

Dữ liệu vào được cung cấp từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) (\(1 \le k \le n \le 3000\)), lần lượt là số lượng phần tử của mảng và số lượng mảng con cần chia.
• Dòng thứ hai chứa \(n\) số nguyên \(x_1, x_2, \ldots, x_n\) (\(1 \le x_i \le 10^5\)), là nội dung của mảng.

Output

In ra một số nguyên duy nhất là tổng chi phí tối thiểu tìm được.

Example

8 3
2 3 1 2 2 3 4 1

110

Scoring

• Subtask \(1\) (\(30\%\) số điểm) : \(1 \leq k \leq n \leq 20\).
• Subtask \(2\) (\(30\%\) số điểm) : \(1 \leq k \leq n \leq 300\).
• Subtask \(3\) (\(40\%\) số điểm) : \(1 \leq k \leq n \leq 3000\).