Ярослав играет в игру «Время». В игре у него есть таймер, на котором изображено время, которое ему осталось жить. Как только таймер показывает 0, игровой персонаж Ярослава умирает и игра заканчивается. Так же в игре существует n часовых станций, станция номер i находится в точке (x_i, y_i) плоскости. Зайдя на станцию номер i, игрок увеличивает текущее время на своем таймере на a_i. Станции одноразовые, то есть если игрок второй раз зайдет на какую-нибудь станцию, то время на его таймере не увеличится.

На перемещение между станциями игрок тратит d·dist единиц времени, где dist — расстояние, пройденное игроком, а d — некоторая константа. Расстояние между станциями i и j определяется как |x_i - x_j| + |y_i - y_j|.

Изначально игрок находится на станции номер 1, и у игрока осталось строго больше нуля и меньше одной единицы времени. На станции номер 1 за единицу денег можно увеличить время на таймере на единицу времени (можно покупать только целое количество единиц времени).

Сейчас Ярослава интересует вопрос: сколько единиц денег нужно ему, чтобы попасть на станцию номер n? Помогите Ярославу. Считайте, что время покупки и увеличения времени на таймере пренебрежимо мало.