Description

A sequence of integer numbers is called strictly monotonically increasing if every term of the sequence is strictly greater than the one preceding it. A strictly monotonic sequence is a sequence that is strictly monotonically increasing. A sequence of integers is called k-monotonic if it can be decomposed into k disjoint contiguous subsequences that are strictly monotonic. For example a strictly monotonically increasing sequence is 1-monotonic in fact it is k-monotonic for every k between 1 and the number of elements it contains. The sequence { 1, 2, 3, 1, 2 } is 2-monotonic since it can be decomposed into { 1, 2, 3 } and { 1, 2 }. If a sequence is not k-monotonic, you can transform it into a k-monotonic sequence by performing the following operation one or more times: select any term in the sequence and either increase it or decrease it by one. You are allowed to perform any number of these operations on any of the terms. Given a sequence of numbers A1, A2, , An and an integer k, you are to calculate the minimum number of operations required to transform the given sequence into a k-monotonic sequence.

Input

The input contains multiple test cases. Each test case contains consists of two lines. The first line gives the integers n (1 n 100) and k (1 k n). The second line gives the integers A1, A2, , An (-100000 Ai 100000). A pair of zeroes indicates the end of the input and should not be processed.

Output

Output the answer of each test case on a separate line.

Sample Input

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

Sample Output

4 2 0 9 2

Author

windy7926778