Беси участвует в марафоне.
Маршрут марафона состоит из N контрольных точек (3 <= N <= 500),
которые надо посетить по порядку, причём контрольная точка 1 -
старт, контрольная точка N - финиш.
Беси решил пропустить до K (K сократить себе маршрут. Она не может пропустить контрольные точки
1 и N.
Определите минимальное расстояние которое пробежит Беси, если она
может пропустить до K контрольных точек.
Поскольку марафон проводится на улицах Манхэттена, то и расстояние
между точками (x1, y1) и (x2, y2) нужно определять манхэттенское:
|x1-x2| + |y1-y2|.
INPUT: (файл marathon.in)
В первой строке задаются N и K.
Каждая из следующих N строк содержит два разделённых пробелом целых
числа x и y, представляющих контрольную точку (-1000 <= x <= 1000,
-1000 <= y <= 1000). Контрольные точки даны в порядке, в котором они
должны посещаться.
Заметим, что маршрут марафона может самопересекаться несколько раз
и некоторые контрольные точки могут быть в одной и той же позиции.
Когда Беси пропускает контрольную точку в некоторой позиции, она
пропускает только экземпляр контрольной точки, а не все контрольные
точки в этой позиции.
Формат выходных данных
Выведите миниальное расстояние, которое Беси может пробежать,
пропустив до K контрольных точек. В данном примере, пропустив
точки (8,3) и (10,-5) она пробежит минимальное растояние, равное 4.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2
0 0
8 3
1 1
10 -5
2 2
|
4
|