# [Usaco2014 Dec]Marathon

时间限制：10s 【提交】 空间限制：128MB

### 题目描述

Unhappy with the poor health of his cows, Farmer John enrolls them in an assortment of different physical fitness activities. His prize cow Bessie is enrolled in a running class, where she is eventually expected to run a marathon through the downtown area of the city near Farmer John's farm! The marathon course consists of N checkpoints (3 <= N <= 500) to be visited in sequence, where checkpoint 1 is the starting location and checkpoint N is the finish. Bessie is supposed to visit all of these checkpoints one by one, but being the lazy cow she is, she decides that she will skip up to K checkpoints (K < N) in order to shorten her total journey. She cannot skip checkpoints 1 or N, however, since that would be too noticeable. Please help Bessie find the minimum distance that she has to run if she can skip up to K checkpoints. Since the course is set in a downtown area with a grid of streets, the distance between two checkpoints at locations (x1, y1) and (x2, y2) is given by |x1-x2| + |y1-y2|.

### 输入格式

### 输出格式

### 样例输入

5 2 0 0 8 3 1 1 10 -5 2 2

### 样例输出

4

### 提示

没有写明提示

### 题目来源

Silver