This problem is from hackerearth

Problem

Summer break is almost here and to earn a little money you have decided to work at candy shop. At the candy shop you are in charge of assigning salesmen to counters. There are N counters numbered 1 to N. Counter i has Ci candies. Each counter must be assigned to exactly one salesman. There are K (K <= N) salesmen and you should assign only adjacent counters to each salesman.

Salesmen have decided to ask for bonuses from the boss, and each will get an amount equivalent to the product of the number of counters he has been assigned and the sum of the candies in each of those counters.

Your boss has asked you to find the minimum total bonus he has to give.

Input

The first line will contain two integers N and K. Each line i of the next N lines will contain a single integer describing the value of Ci

Output

Print a single integer denoting the minimum total bonus the boss has to give to his employees.

Constraints

1<= N <= 5000 1<= K <= 500 1 <= Ci <= 10^9

Thanks