The supervillains of the Marvel universe have formed a very strong chain to defeat the Avengers . Nick Fury has thought of a plan to beat the villains and he needs your help . Each villain has a strength value given by an integer .The avengers can divide the chain into K smaller sub-chains . The strength of each villain in any sub-chain is multiplied by the number of villains in their sub-chain . You have to divide the chain in such a way that the total strength of the villains is minimum . You will be given an array of N integers , each integer specifying the strength of the villain in that position in the chain . You have to print the minimum total strength of the villains after breaking the chain.

Input

First line contains two integers N and K denoting the number of avenger and the number of sub-chains. The next line contains N integers where ith integer denotes the strength value of ith avenger .

Output

In the single line print the minimum total strength.

Constraints

1 <= N <= 8000

1 <= K <= 800

1 <= Ai <= 10⁹

Ai is the strength value of ith avenger. K is always less than N.