Phân chia khoáng sản

Trong một vương quốc nọ, có một mỏ khoáng sản quý hiếm trải dài theo một con suối. Mỏ được chia thành \(L\) khu vực, được đánh số từ \(1\) đến \(L\). Mỗi khu vực thứ \(i\) chứa một lượng khoáng sản có giá trị là \(C_i\). Vua của vương quốc muốn thuê \(G\) đội thợ mỏ để khai thác toàn bộ mỏ khoáng sản này.

Để việc khai thác được hiệu quả và công bằng, nhà vua quyết định chia con suối thành \(G\) đoạn liên tiếp, và mỗi đội thợ mỏ sẽ chịu trách nhiệm khai thác một đoạn. Chi phí cho việc khai thác một khu vực được tính bằng cách lấy giá trị khoáng sản của khu vực đó nhân với tổng số khu vực trong đoạn mà nó thuộc về. Tổng chi phí khai thác của cả mỏ sẽ là tổng chi phí của tất cả các khu vực.

Nhà vua muốn tìm cách phân chia mỏ khoáng sản thành \(G\) đoạn sao cho tổng chi phí khai thác là nhỏ nhất. Bạn, một vị quan cận thần tài ba, được giao nhiệm vụ tìm ra cách phân chia tối ưu này.

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 \(L\) và \(G\) (\(1 \le L \le 8000\), $1 \le G \le min(800, L) $).
• \(L\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(C_i\) (\(1 \le C_i \le 10^9\)), là giá trị của dãy số.

Output

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

Example

6 3
11 11 11 24 26 100

299

Scoring

• Subtask \(1\) (\(30\%\) số điểm) : \(1 \leq L \leq 20\).
• Subtask \(2\) (\(30\%\) số điểm) : \(1 \leq L \leq 800\).
• Subtask \(3\) (\(40\%\) số điểm) : \(1 \leq L \leq 8000\).