На болоте

Добрался Иван-царевич до болот, тут они с волком и простились. Пригляделся Иван-царевич, и стрелу свою увидел: торчит она в самой дальней кочке. Ну что ж, делать нечего, придется прыгать с кочки на кочку, чтобы до нее добраться.

Ваша задача - определить наиболее короткий маршрут до стрелы.

Формат входного файла input.txt

Первая строка - целое число N (1 <= N <= 500) - количество кочек на болоте.

Далее следуют N строк, описывающие кочки. Строка № j+1 (j = 1, 2, …, N) содержит 0 или более пар, состоящих из целого числа P_k (1 <= P_k <= N, j < k < N) и вещественного числа Q_k (0,001 <= Q_k <= 1000, j < k < N) через пробел (пары также разделены пробелами). Целое число P_k (первое в паре) - номер кочки, вещественное число Q_k - расстояние от кочки № j до кочки № P_k. Каждая из N строк завершается парой 0 0.

При этом первая строка описывает кочку, на которую Иван-царевич встает первой, а последняя - кочку, до которой и нужно добраться.

Обратите внимание, что во входном файле указаны расстояния только между такими парами кочек № j и № P_k, в которых j < P_k. Расстояние от кочки № P_k до кочки № j в точности равно расстоянию от кочки № j до кочки № P_k. Гарантируется, что путь от кочки № 1 до кочки № N всегда существует.

Примечание. Поскольку Иван-царевич может прыгнуть не далее определенного расстояния, во входном файле указаны только принципиально достижимые для него кочки, когда он стоит на кочке №j.

Формат выходного файла output.txt

Первая строка - вещественное число S с точностью до 2 знаков после запятой - минимальное расстояние, которое придется преодолеть Ивану-царевичу, добираясь до стрелы.

Пример входного файла

3

2 4.6 3 5.1 0 0

0 0

0 0

Пример выходного файла.

5.10