题目描述

一个整数序列如果每一项都严格大于前一项，则称为严格单调递增序列。类似地，如果每一项都严格小于前一项，则称为严格单调递减序列。严格单调序列是指要么严格单调递增，要么严格单调递减的序列。一个整数序列被称为$k$-单调的，如果它可以被分解为$k$个不相交的连续子序列，且每个子序列都是严格单调的。

例如，严格单调递增序列是$1$-单调的——实际上，对于$1$到序列元素个数之间的任意$k$，它都是$k$-单调的。序列$\{1, 2, 3, 2, 1\}$是$2$-单调的，因为它可以被分解为$\{1, 2, 3\}$和$\{2, 1\}$。

如果一个序列不是$k$-单调的，你可以通过执行以下操作一次或多次来将其转换为$k$-单调序列：选择序列中的任意一项，并将其增加或减少$1$。你可以对任意项执行任意次数的此类操作。给定一个数字序列$A_1, A_2, \ldots, A_n$和一个整数$k$，你需要计算将给定序列转换为$k$-单调序列所需的最小操作次数。

输入格式

输入包含多个测试用例。

每个测试用例由两行组成。第一行给出整数$n$（$1 \leq n \leq 1000$）和$k$（$1 \leq k \leq \min\{n, 10\}$）。第二行给出整数$A_1, A_2, \ldots, A_n$（$-100\,000 \leq A_i \leq 100\,000$）。

输入以两个$0$表示结束，且不应处理。

输出格式

每个测试用例的答案单独占一行。

输入样例 1

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

输出样例 1

4
2
0
9

题目来源

POJ Monthly--2006.09.29, ACRush, 改编自TopCoder SRM 309 KMonotonic