Start: 2025-01-06 00:00:00

25金华第二届信息联赛复盘

End: 2025-01-18 00:00:00
Now  2025-04-16 07:57:57  类型: IOI  状态: Ended 

P4. 打妖怪
Description

去山顶的路上有n个妖怪,起点在1,终点在n,可以跳过k个妖怪不打,但是第1个和第n个妖怪不能跳过,必须要打,因为已经被发现了。

如果2个妖怪的位置是(x_1,y_1),(x_2,y_2),在崎岖的上路中,他们俩之间的距离就是|x_1-x_2|+|y_1-y_2|

打怪顺序是按顺序打怪!


Input

第一行两个整数n,k,用空格隔开

接下来n行,每行两个整数x,y表示妖怪的位置

注意,妖怪的位置可能重合,这样子,他就只能跳1个

Output

一个正整数,表示他去山顶的最短距离

Examples

Input

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

Output

4
Hint

20%数据:k,n\leq 10

50%数据:k,n\leq 100

100%数据:k,n\leq 500,-1000\leq  x,y \leq 1000


Submit

题目参数
Time Limit 1 second
Memory Limit 512 MB
Submit