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.

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~. 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.

Input

• 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)~.

Output

Một dòng duy nhất chứa chi phí nhỏ nhất.

Scoring

Sample Input 1

6 3
11
11
11
24
26
100

Sample Output 1

299

Notes

• Cách chia tối ưu là ~(11, 11, 11), (24, 26), (100)~;

• Chi phí là ~11 \cdot 3 + 11 \cdot 3 + 11 \cdot 3 + 24 \cdot 2 + 26 \cdot 2 + 100 \cdot 1 = 299~.