Monotonic

给定一个长度为 $n$ 的整数序列 $C_1,C_2,\ldots,C_n$。你需要将其划分为恰好 $m$ 个非空连续子段。

对于每个子段，可以将其中的元素修改为一个整数序列 $D$。修改后的序列必须严格递增，即 $D_1<D_2<\cdots<D_k$；或严格递减，即 $D_1>D_2>\cdots>D_k$。每个子段可以独立选择递增或递减。

一个子段的修改代价为

$$\sum_{i=1}^{k}\lvert D_i-C_i\rvert。$$

求所有子段的修改代价之和的最小值。

例如，序列 $1,2,3,2,1$ 可以被划分为 $2$ 个满足要求的单调子段 $(1,2,3)$ 和 $(2,1)$。将序列 $1,1,1,1$ 修改并划分为 $2$ 个单调子段时，最优方案为 $(1,2)$ 和 $(2,1)$，总代价为 $2$。

输入格式

第一行包含两个整数 $n,m$。

接下来 $n$ 行，每行包含一个整数，依次给出 $C_1,C_2,\ldots,C_n$。

输出格式

输出一个整数，表示最小的修改代价之和。

样例输入

6 1
1
2
3
3
2
1

样例输出

9

数据范围

• 对于 $30\%$ 的数据，$n\le 100$；
• 对于 $20\%$ 的数据，$m=1$；
• 对于 $100\%$ 的数据，$n\le 2000$，$m\le\min\{n,10\}$，$C_i\le 10^4$。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

6 1
1
2
3
3
2
1

输出

9