Cho dãy \(L\) gồm các số \(C[1..L]\), cần chia dãy này thành \(G\) đoạn liên tiếp. Với phần tử thứ \(i\), ta định nghĩa chi phí của nó là tích của \(C_i\) và số lượng các số nằm cùng đoạn liên tiếp với \(C_i\). Chi phí của dãy số ứng với một cách phân hoạch là tổng các chi phí của các phần tử của G đoạn đã chia.

Yêu cầu: Hãy xác định cách phân hoạch dãy số để chi phí là nhỏ nhất.

Input

• Dòng đầu tiên chứa 2 số \(L\) và \(G\).
• \(L\) dòng tiếp theo, chứa giá trị của dãy \(C_1, C_2, …, C_n\).

Output

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

Scoring

• \(1 ≤ L ≤ 8000\).
• \(1 ≤ G ≤ 800\).
• \(1 ≤ C_i ≤ 10^9\).

Example

6 3
11
11
11
24
26
100

299