题目描述

给定一个长度为 $n$ 的序列 $c_{1\cdots n}$，我们称 $c$ 的单调序列就是把它改成一个严格单调递增的序列 $d_{1\cdots n},\forall i\in[1,n)\wedge d_i>d_{i+1}$，同时我们定义它的代价就是 $\sum_{i=1}^n |c_i-d_i|$。

这个问题你是不是看得非常眼熟呢? 下面请考虑这个问题的加强版吧。

请你把这个长度为 $n$ 的序列分成 $m$ 段，其中要求将每段改成一个单调序列，同时要求代价和最小．比如说 $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\cdots n}$。

输出格式

一个数，即最小的代价和。

6 1
1
2
3
3
2
1

9

数据规模与约定

对于 $30\%$ 的数据，$1\leq n\leq 100$。

另外 $20\%$ 的数据，$m=1$。

对于 $100\%$ 的数据，$1\leq n\leq 2\times 10^3$，$1\leq m\leq \min\{n,10\}$，$c_i\leq 10^4$。