1947. 马拉松2

【题目描述】

因为担心牛们的健康问题，FJ把为它们报了各种健身训练班。他最引以为傲的奶牛Bessie加入了一个长跑训练班，它期待自己经过训练之后能去参加马拉松比赛，赛场离FJ的牧场不远，需要穿过镇子。

马拉松场地由N（3 <= N <= 500）个检查站组成，选手需要按顺序经过这N个检查站，1号检查站为起点，N号检查站为终点，按规定Bessie也必须这样做，但是这个懒丫头决定偷个懒，它要跳过不超过K(K < N)个检查站以缩短赛程。不过，它还算有节制，不会跳过起点和终点，毕竟这样做显得太不尊重举办方了。

请帮Bessie计算一下，如果要跳过不超过K个检查站的话，它的最小行程是多少。

由于赛场是一块划分成网格的空地，站与站之间距离的计算方法是：如果两个检查站的坐标分别为（x1,y1）和(x2,y2)，则它们之间的距离为|x1-x2|+|y1-y2|。

【输入格式】

第一行有两个整数，即N和K；

接下来有N行，每行有两个空格隔开的整数，x和y，表示一个检查站的坐标。检查站给出的顺序正是比赛时要求依次经过的顺序。注意跑步的路线有可能跟自己有若干次的交叉，也就是说会有一些检查站设在同一个位置，当Bessie决定跳过一个这样的检查站时，不意味着它要把设在这个点的检查站全都跳过。

【输出格式】

输出Bessie跳过不超过K个检查站后的最小行程数。

【样例输入】

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

【样例输出】

4

【提示】

样例解释：

跳过(8, 3)和(10, -5)两个点，得到最小行程为4.

【来源】

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|.

INPUT:

The first line gives the values of N and K.

The next N lines each contain two space-separated integers, x and y,

representing a checkpoint (-1000 <= x <= 1000, -1000 <= y <= 1000).

The checkpoints are given in the order that they must be visited.

Note that the course might cross over itself several times, with

several checkpoints occurring at the same physical location.  When

Bessie skips such a checkpoint, she only skips one instance of the

checkpoint -- she does not skip every checkpoint occurring at the same

location.

SAMPLE INPUT:

5 2

0 0

8 3

1 1

10 -5

2 2

OUTPUT:

Output the minimum distance that Bessie can run by skipping up to K

checkpoints.  In the sample case shown here, skipping the checkpoints

at (8, 3) and (10, -5) leads to the minimum total distance of 4.

SAMPLE OUTPUT:

4