Marathon 2

Farmer John decided that his cows were out of shape, so he organized a marathon for them. Bessie, his favorite cow, is going to run it.

The course consists of $N$ checkpoints. The marathon starts at checkpoint 1, visits every checkpoint in index order, and finishes at checkpoint $N$. Bessie is lazy. She will run the race, but she wants to secretly skip up to $K$ of the checkpoints in the middle. Skipping checkpoint 1 or checkpoint $N$ would be far too obvious, so she leaves those two alone.

If Bessie skips at most $K$ checkpoints, what is the shortest distance she has to run?

The race is held in the middle of the city, so distances are taxicab (Manhattan) distances. The distance between $(x_1, y_1)$ and $(x_2, y_2)$ is $|x_1 - x_2| + |y_1 - y_2|$, where $|x|$ denotes absolute value.

The first line contains the number of checkpoints $N$ and the number of checkpoints Bessie may skip $K$ ($3 \le N \le 500$, $0 \le K < N$).

Each of the next $N$ lines contains two integers. The first integer on line $i$ is the $x$ coordinate of checkpoint $i$ and the second is its $y$ coordinate ($-1000 \le x \le 1000$, $-1000 \le y \le 1000$).

Two checkpoints may share the same coordinates. When Bessie skips a checkpoint she skips only that index, not every checkpoint located at that point.

Print the shortest distance Bessie can run while skipping at most $K$ checkpoints.

In the first example Bessie skips checkpoints 2 and 4, so she runs $(0, 0)$, $(1, 1)$, $(2, 2)$ for a total distance of 4. No route is shorter.