Since Max is wasting his time in his List I Communication credit lecture, he decided to start taking subsequences of arrays instead!
Specifically, he has integers,
, and wants to take a subsequence of length
, but to make his life even harder, his List I Communication credit professor adds a restriction: he must find the subsequence that has a length of
with the minimum sum of the absolute difference between consecutive terms.
That is, he must minimize , where
is the
element of his subsequence and
denotes the absolute difference between
and
.
Can you find the minimum sum of absolute differences for every possible subsequence of length ?
Constraints
Subtask 1 [40%]
Subtask 2 [60%]
No additional constraints.
Input Specification
The first line will contain two integers, and
, the array's length and the subsequence's length, respectively.
The second line will contain integers,
, the elements of the array.
Output Specification
Output the minimum sum of absolute differences between consecutive elements for any subsequence of length .
Sample Input 1
6 2
1 5 6 2 1 3
Sample Output 1
0
Explanation for Sample 1
It can be proven that the minimal sum is achieved with the subsequence .
Sample Input 2
6 4
3 2 6 2 7 9
Sample Output 2
6
Explanation for Sample 2
It can be proven that the minimal sum is achieved with the subsequence .
Comments
Since the original data were weak, an additional test case was added to each subtask, and all submissions were rejudged.