Minimize Bookshelf Messiness

Frank is a very neat person who loves his bookshelf. He has a lot of books, each with a unique height, and he arranges them on his shelf in increasing height order. However, the books come in different widths, and the shelf still looks untidy. Frank decides to remove k books so that the shelf looks as neat as possible.

The "messiness" of the bookshelf is defined as the sum of absolute differences of the widths of every two adjacent books. For example, suppose there are 4 books:

1 × 2
5 × 3
2 × 4
3 × 1

After arranging by height (the height values are distinct) the order becomes:

1 × 2
2 × 4
3 × 1
5 × 3

The messiness is calculated as:

[ |4-2| + |1-4| + |3-1| = 2 + 3 + 2 = 7. ]

Given that Frank removes exactly k books, your task is to select the remaining n - k books (keeping the order) such that the messiness is minimized. Compute the minimum possible messiness.

inputFormat

The first line contains two integers n and k (where 0 ≤ k < n), representing the total number of books and the number of books Frank will remove, respectively.

The second line contains n integers, representing the widths of the books in the order of increasing height.

outputFormat

Output a single integer indicating the minimum messiness after removing exactly k books.

sample

4 0
2 4 1 3

7