跳石头，搭梯子

题号：NC252739
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

牛牛实在是太胖了，所以牛妹给牛牛安排了一个跳石头的任务。

牛妹在牛牛面前放置了一排 $n$ 个石头，第 $i$ 个石头的高度记为 $h[i]$ 。

最开始牛牛在第 1 个石头上面，牛妹需要牛牛跳跃到第 $n$ 块石头上。

牛牛每次跳跃只能从第 $i$ 块石头跳跃到第 $i+1$ 块石头上，这会给牛牛增加 $|h[i]-h[i+1]|$ 的疲劳值，为了降低跳到第 $n$ 块石头上的疲劳值牛牛将会搭建不超过 $m$ 个梯子。

牛牛能在第 $x$ 和第 $y$ 块石头间搭建梯子需要对所有的 $j(x<j<y)$ 都有： $h[j] < h[x]$ 和 $h[j] < h[y]$ 。

若第 $x$ 和第 $y$ 块石头间存在一个梯子那么牛牛可以直接从第 $x$ 块石头爬向第 $y$ 块石头，这会给牛牛增加 $|h[x]-h[y]|$ 的疲劳值。

现在给定 $n$ 和 $m$ 以及所有石头的高度，你能帮牛牛判断在最优搭建梯子的方式下其到达第 $n$ 块石头上的最小疲劳值是多少吗？

第一行输入两个空格分隔的整数： $n\ m$ 。

接下来一行输入 $n$ 个空格分隔的整数： $h[1],h[2],h[3],...,h[n]$ 。

保证：

$2 \le n \le 2\times 10^5$

$1 \le m \le 2\times 10^5$

$0 < h[i] \le 10^9$

输出一行一个整数代表牛牛到达第 n 块石头上的最小疲劳值。

示例1

复制

13 3
5 3 6 8 6 9 9 1 7 4 5 4 9

复制

示例2

复制

6 1
7 1 8 3 2 5

复制

在第 1 和第 3 个石墩之间搭建梯子即可