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. Similarly, a sequence is called strictly monotonically decreasing if every term is strictly less than the one preceding it. A strictly monotonic sequence is a sequence that is either strictly monotonically increasing or decreasing. 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, 2, 1 } is 2-monotonic since it can be decomposed into { 1, 2, 3 } and { 2, 1 }.

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 A₁, A₂, …, A_n 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 ≤ 1000) and k (1 ≤ k ≤ min{ n, 10 }). The second line gives the integers A₁, A₂, …, A_n (−100 000 ≤ A_i ≤ 100 000).

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.

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
0 0

4
2
0
9

Source

POJ Monthly--2006.09.29, ACRush, modified from TopCoder SRM 309 KMonotonic