题目描述

你已经做了 blg 出的 $9$ 道烂题了，他已经被你骂惨惨惨了，但没关系，他脸皮更厚了，坚持要出 $n$ 道烂题。

假定 blg 出了 $n$ 个题目，并打算将其全部用于 $m$ 场比赛中。很显然，同一道题目不会出现在不同的比赛中。

第 $i$ 个题目的思维难度为 $a_i$。为了方便整理试卷，同一场比赛只能用连续编号的题。

如果我们将第 $l$ 道题至第 $r$ 道题放到第 $j$ 场比赛，则第 $j$ 场比赛中题目的难度跨度为 $b_j=max(a_l...a_r)-min(a_l...a_r)$。

例如，第 $j$ 场比赛使用第 $l\sim r$ 题，假定 $a_{l\sim r}=[1,3,5,7,8,6,4,2]$，那么本场比赛的难度跨度为 $b_j=8-1=7$。

blg 的目标是合理将这些题目分配到各场比赛中，使得对于 $j∈1...m$，有 $\sum b_j$ 最小。

注意，同一场比赛必须使用连续的题目，且所有的题目都必须恰好被使用一次。

输入格式

第一行是两个整数 $n$ 和 $m$。

接下来一行有 $n$ 个数字，第 $i$ 个数字表示第 $i$ 题的思维难度 $a_i$。

输出格式

一个数字，表示各场考试的难度跨度之和的最小值。

测试样例

5 2
3 2 1 4 5

3

7 3
1 3 1 4 5 2 1

4

6 3
1 8 11 18 21 28

13

样例说明

样例1中，把前三个题目分到一组，后两个题目分到一组。难度跨度之和为 $2+1=3$。

样例2中，前三个题目一组，接下来两个题目一组，最后两个题目一组。难度跨度之和为 $2+1+1=4$。

样例3中，第一个数一组，最后一个数一组，剩下的数一组。难度跨度之和为 $0+13+0=13$。

数据规模说明

对 $30\%$ 的数据，$1≤m≤n≤20$。

对 $100\%$ 的数据，$1≤m≤n≤500$，$1≤a_i≤10^9$。