P1103 Book Arrangement

Frank is a neat person. He has a large pile of books and a bookshelf, and he wants to put the books on the shelf. The shelf can hold all the books, so Frank first arranges the books on the shelf in order of height. However, Frank finds that since many books have different widths, the shelf still looks messy. He decides to remove $k$ books so that the shelf looks tidier. The messiness of the shelf is defined as the sum of the absolute differences of the widths between each pair of adjacent books (after ordering by height). For example, there are $4$ books: $1 \times 2$ $5 \times 3$ $2 \times 4$ $3 \times 1$ After arranging them by height, Frank gets: $1 \times 2$ $2 \times 4$ $3 \times 1$ $5 \times 3$ The messiness is $2+3+2=7$. Each book has a distinct height. Please find the minimum possible messiness after removing $k$ books.

The first line contains two integers $n$ and $k$, the number of books and the number to remove ($1 \le n \le 100$, $1 \le k < n$). Each of the next $n$ lines contains two integers, the height and width of a book, both no more than $200$. Heights are guaranteed to be distinct.

Output a single integer: the minimum messiness of the shelf.

Translated by ChatGPT 5