Description

Robby bought a new bookshelf, and he wanted to put all his N books on it. The bookshelf contains K layers, and the heights of each layer are variable. That is, the minimum height of one layer is equal to the maximum height of all the books in this layer. And the height of the bookshelf is the sum of all layers' heights. Now Robby wants to make the height of his bookshelf as low as possible, but he don't want to break the order of the books, that is, each layer must contain the consecutive books of the original book series. And each layer must contain at least one book.

Input

There are several test cases in the input. The first line of each test case contains two integers N and K (1 K N 100). The second line contains N integers, indicating the heights of the books. You can assume the height of every book is no more than 1000. The input is terminated with N = K = 0.

Output

Output one line for each test case, that is, the minimum height of the bookshelf.

Sample Input

4 2 1 4 2 3 4 2 4 1 2 3 4 4 1 2 3 4 0 0

Sample Output

5 7 10

Hint

For the first sample, the best strategy is 1+max(4,2,3)=5 For the second sample, the best strategy is max(4,1,2)+3=7 For the third sample, the best strategy is 1+2+3+4=10

Source

TJU Programming Contest 2007 by RoBa