## Max's Anger Contest Series 1 P5 - Slacking Subsequences

View as PDF

Points: 15 (partial)
Time limit: 4.0s
Memory limit: 1G

Author:
Problem types

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 ?

#### 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 .