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.

Dữ liệu vào :

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

Kết quả:

Chi phí nhỏ nhất để phân hoạch.

Ràng buộc:

~1 \le L \le 8000~

~1 \le G \le 800~

~1 ≤ C_i \le 10^9~

Ví dụ

Dữ liệu vào

6 3
11
11
11
24
26
100

Dữ liệu ra

299

Giải thích:

• Cách tối ưu: C[]=(11,11,11), (24,26), (100).
• Chi phí 11*3 + 11*3 + 11*3 + 24*2 + 26*2 + 100*1=299