Description

若一个整数序列的每一项都严格大于它前面的项，则称之为严格单调递增序列。类似地，若一个序列的每一项都严格小于它前面的项，则称之为严格单调递减序列。严格单调序列是严格单调递增或递减的序列。若一个整数序列可以分解为严格单调的k个不相交的连续子序列，则称之为$k$-单调序列。一个严格单调递增序列是$1$-单调序列，事实上它也是$k$-单调序列。序列{1,2,3,2,1}是$2$-单调的，因为它可以被分解为{1,2,3}和{2,1}。若序列不是$k$-单调序列，则可以通过一次或多次进行以下操作将其转换为$k$-单调序列：选择序列中的任意项，将其增加或减少$1$。给定一个数字序列$A_1,A_2,…,A _n$和一个整数$k$，计算将给定序列转换为$k$-单调序列所需的最小成本。

Format

Input

输入包含多个测试用例，每个测试用例都包含两行。第$1$行给出整数$n$$（1≤n≤1000）$和$k（1≤k≤min${n,10}$）$；第$2$行给出整数$A_1,A_2,…,A _n（-10^5≤A_ i≤10^5）$。最后两个$0$表示结束。

Output

对每个测试用例，都单行输出答案。

Samples

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

来源

POJ3016