У нас было 2 набора юного химика, 75 мятных таблеток, 5 упаковок оберточной бумаги, полфунта детских драже и целое множество подарков всех сортов и расцветок, а также машинки, куклы, мешок вкусного оленьего корма, пинта чистого сока и стадо быстрых оленей.
Не то что бы это был необходимый запас для поездки. Но если начал развозить подарки, становится трудно остановиться.
Единственное что вызывало у меня опасение - это олени. Нет ничего более непредсказуемого, чем стадо северных оленей, кто знает чего от них ожидать? Я догадывался, что рано или поздно они дадут о себе знать.
Самое страшное, что домов, куда нужно доставить подарки, более 10^100000000 и ребенок сильно расстроится, узнав, что не получил подарка на Новый Год. Этого допускать нельзя, благо вы - не единственный Санта, и вам будет достаточно доставить подарки только в своем городе. Детишек в вашем городе не больше 10^4, но все они живут в разных домах. У вас есть список, в котором не больше 10^4 элементов, каждый элемент списка представляет собой 2 целых числа – координаты дома следующего ребеночка. Доставив подарки в очередной дом, вы, как порядочный Санта, обязаны стирать координаты этого дома из своего списка. Но ваши олени не хотят спокойно доставлять подарки, они коллективно прокладывают на их взгляд более оптимальный и правильный маршрут, и выбирают номер следующего дома из вашего списка по своей очень логичной и тривиальной формуле:
Nnext = |(K1 - K2 ) *R|% L,
где Nnext – номер следующего дома в вашем списке (Как делают настоящие ТРУ-программисты? Они считают элемент с единицы нуля!) K1 - количество еще не посещенных домов, K2 – количество уже посещенных домов, R – коэффициент рандомности стада и L – длина текущего списка. Заметим, что после посещения дома, количество элементов в вашем списке уменьшается, вы же порядочный Санта, верно? Вечером, после тяжелого трудового дня, вы, как и остальные труженики Новогоднего фронта, выкладываете в свой блог количество километров, которые сегодня преодолели. Изначально вы находитесь в доме с индексом 0 и считается, что подарок в этот дом уже доставлен. Зная столь тривиальную, понятную и очевидную формулу расчета следующего дома, а также имея список домов и хорошо зная свое стадо, вплоть до их коэффициента рандомности, скажите какое расстояние вы пройдете за всю поездку? Ответ округлите вверх до целых, в таких вещах можно чуть-чуть преувеличить.
Входные данные:
В первой строке входного файла находятся целые положительные числа N, R (1<N<=10000,1< R <1000000) – количество детей в вашем списке и коэффициент рандомности вашего стада, соответственно.
В следующих N строках находятся по 2 целых числа X,Y (-100000<=X,Y<=100000) – координаты конкретного дома.
Выходные данные:
Выведете одно целое число – ответ на поставленную задачу.
Пример, как же без примера:
Входит:
4 2
1 1
0 0
2 0
2 1
Выходит:
6
(с) Ярослав Свиридов 10и