002 - マラソン

時間制限 5 秒 / メモリ制限 64 MB / 得点 100 / x 6 /

TLE
5sec
MLE
64MB
得点
100

問題

冬。とある H 高校では, マラソンが行われます.

H 高校のマラソンでは, N 個のチェックポイントがあり, 開始地点である 1 から順に, 2, 3, ..., そして終了地点である N まで訪れます. それぞれのチェックポイントは 座標(xi, yi) で表され, チェックポイント i から j に移動するとき |xi - xj| + |yi - yj| ( |x|は x の絶対値) の距離を走る必要があります.

H 高校のなかむらくん(仮名)も この行事の参加を強いられ, N 個のチェックポイントを 1 から順に全て訪問することになりました. しかし, 眠いし寒いし疲れるのであまり走りたくありません. そこでなかむらくんは, 走った距離をごまかすことにしました.

チェックポイントを K 回まで飛ばすことができるとき, なかむらくんが走る最小距離を求めてください. 複数のチェックポイントを連続で飛ばすことも可能ですが, 開始地点 1 と終了地点 N は, 流石に先生に見つかるので飛ばすことができません.

入力

N K
x1 y1
x2 y2
:
xN yN

1 行にチェックポイントの個数 N と 飛ばすことができるチェックポイントの数 K が半角空白区切りで与えられる．

つづく N 行に, チェックポイントの位置が与えられる. このうち i 行目(1 ≤ i ≤ N) の整数 xi, yi は、チェックポイント i が 座標(xi, yi) にあることを意味する.

制約

  • 2 ≤ N ≤ 500
  • 0 ≤ K ≤ N
  • -1000 ≤ xi, yi ≤ 1000

いくつかのチェックポイントが同じ座標に存在する可能性があることに注意すること.

出力

チェックポイントを K 回まで飛ばすことができるときの, 走る最小距離を求めよ.

なかむらくんは, 歩くことなく常に走ることを仮定して良い.

入出力例

入力例 1

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

出力例 1

4

チェックポイント 2 の (8, 3), チェックポイント 4 の(10, -5) を飛ばしたとき, 距離は 4 となる.

入力例 2

2 2
0 0
1000 1000

出力例 2

2000

なかむらくんは不運にも, 開始地点から終了地点で走る必要があります.