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（-105≤A_ i≤105）$。最后两个$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