SEQPART

Hôm nay là buổi học đầu tiên trong kỳ quân sự của Bình và Tuấn. Vì biết hai bạn này từng học chuyên Tin nên thầy đại đội trưởng đã ra yêu cầu cho hai bạn như sau:

Cho danh sách $L$ sinh viên gồm các số $C_1,C_2,\dots ,C_L$ là mã số sinh viên. Hai bạn cần chia dãy này thành $G$ trung đội, mỗi trung đội gồm các phần tử liên tiếp (mỗi trung đội có ít nhất một sinh viên, mỗi sinh viên thuộc đúng một trung đội).

Với phần tử thứ $i$ (tức là sinh viên thứ $i$), chi phí đăng ký vào trung đội của sinh viên đó là tích của $C_i$ và số lượng sinh viên nằm cùng trung đội với $C_i$ (tính cả sinh viên đó). Chi phí của danh sách ứng với một cách chia trung đội là tổng chi phí của các sinh viên thuộc $G$ trung đội đã chia.

Yêu cầu: Hãy xác định cách chia trung đội để chi phí là nhỏ nhất.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $L,G$.
• $L$ dòng tiếp theo, dòng thứ $i$ chứa số nguyên $C_i$ $(1\le C_i\le {10}^9)$.

Dữ liệu ra

In ra một dòng duy nhất là chi phí nhỏ nhất.

Ràng buộc

• $1\le G\le L\le 8000$, $G\le 800$.
• $1\le C_i\le {10}^9$.

Subtasks

• Subtask 1 ($20\%$ số điểm): $L\le 100$.
• Subtask 2 ($10\%$ số điểm): $G\le 10$.
• Subtask 3 ($70\%$ số điểm): $L\le 8000$, $G\le 800$, $C_i\le {10}^9$.

Ví dụ