Cow Marathon Optimization

Bessie the cow is set to participate in a downtown marathon which has N checkpoints (with \(3 \leq N \leq 500\)) arranged in sequence. The first checkpoint is the starting location and the \(N\)th checkpoint is the finish line. To minimize her running distance, Bessie is allowed to skip up to K checkpoints (with \(K < N\)). Note that she cannot skip the first or the last checkpoint.

The checkpoints are laid out on a city grid. The Manhattan distance between two checkpoints at \((x_1, y_1)\) and \((x_2, y_2)\) is given by \[ |x_1 - x_2| + |y_1 - y_2| \] Your task is to help Bessie choose which checkpoints to skip in order to minimize the total distance she runs, while still following the sequence (after skipping) from the start to the finish.

inputFormat

The first line of input contains two integers N and K.

The next N lines each contain two integers representing the coordinates \(x\) and \(y\) of the checkpoints in the order they must be visited.

Constraints: \(3 \leq N \leq 500\) and \(K < N\).

outputFormat

Output a single integer, the minimum total Manhattan distance that Bessie must run.

sample

4 1
0 0
1 0
2 0
3 0

3