Дистанционный практикум по программированию

Имеется N приборов (устройств). Каждое устройство может иметь несколько подчинённых, соединённых напрямую кабелем. Все приборы имеют уникальные номера от 1 до N. Система образует дерево с корневым прибором с номером 1.

Опрос дерева осуществляется следующим образом. Корневой прибор посылает запрос одновременно всем своим непосредственным подчинённым. Те сразу же, в свою очередь, посылают запросы всем своим подчинённым и так далее.

Для каждого прибора есть свое время обработки T_i мс.

Обработка данных в каждом устройстве происходит следующим образом:

·      Если прибор не имеет подчинённых, то он возвращает своё состояние через T_i мс. Возвращает тому, от кого получен запрос.

·      Иначе, как только он получает данные хотя бы с Х% непосредственно подчинённых приборов, он начинает обрабатывать эту информацию и возвращает результаты через T_i мс.

Определите максимальное Х, при котором опрос произойдёт за время, не превосходящее Т.

Опрос заканчивается, как только корневой прибор соберёт всю необходимую информацию. Временем передачи информации между приборами можно пренебречь. Время обработки корневого прибора не учитывается.

В первой строке входного файла содержатся два целых числа: N (1 ≤ N ≤ 10 000) и Т (0 ≤ Т ≤ 10⁶).

Следующая (N – 1) строка содержит информацию о приборах со 2-го по N-й по одному описанию прибора в строке. Каждая из этих строк содержит два числа: P_i (1 ≤ P_i ≤ N) и T_i (0 ≤ T_i ≤ 100). P_i – номер родительского прибора (то есть прибор, для которого устройство c номером i является подчинённым).

Выведите в выходной файл одно искомое число в процентах с точностью не менее 4 знаков после запятой.

Пример

Поток ввода	Поток вывода
6 3 1 2 2 2 2 1 1 2 1 4	50.00000000