题目描述

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

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

第 $i$ 个题目的思维难度为 $a_i$ ，且保证 $a_i≤a_{i+1}$ 。为了方便整理试卷，同一场比赛只能用连续编号的题。

如果我们将第 $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]$ ，那么本场比赛的难度跨度为 $b_j=8-1=7$ 。

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

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

输入格式

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

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

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

5 2
1 2 4 4 5

5 5
1 2 3 4 5

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

样例2中，每个题目自成一组。难度跨度之和为 $0$ 。

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

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