Ярослав играет в игру «Время». В игре у него есть таймер, на котором изображено время, которое ему осталось жить. Как только таймер показывает 0, игровой персонаж Ярослава умирает и игра заканчивается. Так же в игре существует n часовых станций, станция номер i находится в точке (xi, yi) плоскости. Зайдя на станцию номер i, игрок увеличивает текущее время на своем таймере на ai. Станции одноразовые, то есть если игрок второй раз зайдет на какую-нибудь станцию, то время на его таймере не увеличится.
На перемещение между станциями игрок тратит d·dist единиц времени, где dist — расстояние, пройденное игроком, а d — некоторая константа. Расстояние между станциями i и j определяется как |xi - xj| + |yi - yj|.
Изначально игрок находится на станции номер 1, и у игрока осталось строго больше нуля и меньше одной единицы времени. На станции номер 1 за единицу денег можно увеличить время на таймере на единицу времени (можно покупать только целое количество единиц времени).
Сейчас Ярослава интересует вопрос: сколько единиц денег нужно ему, чтобы попасть на станцию номер n? Помогите Ярославу. Считайте, что время покупки и увеличения времени на таймере пренебрежимо мало.