Опитування приладів
Є N приладів (пристроїв). Кажен пристрій може мати декілька підлеглих, з'єднаних напряму кабелем. Всі прилади мають унікальні номери від 1 до N. Система утворює дерево з коерневим приладом з номером 1.
Опитування дерева здійснюється наступним чином. Кореневий прилад посилає запит одночасно всім своїм безпосереднім підлеглим. Тобто відразу ж, у свою чергу, посилають запити всім своїм підлеглим і так далі.
Для кожного приладу є свій час опрацювання T_i мс.
Опрацювання даних у кожному пристрої відбувається наступним чином:
Якщо прилад не має підлеглих, то він повертає свій стан через T_i мс. Повретає тому, від кого отримано запит.
Інакше, як тільки він отримує дані хоча б від Х% безпосередньо підлеглих приладів, він починає опрацьовувати цю інформацію і повертає результати через T_i мс.
Визначте максимально Х, при якому опитування відбудеться за час, який не перевищує Т.
Опитування завершується, як тільки кореневий прилад збере всю необхідну інформацію. Часом передачі інформації між приладами можна знехтувати. Час опрацювання кореневого приладу не враховується.
Вхідні дані
У першому рядку вхідного файлу містяться два цілих числа: N (1 ≤ N ≤ 10 000) і Т (0 ≤ Т ≤ 10^6).
Наступні (N – 1) рядків містять інформацію про прилади з 2-го по N-й по одному опису прилада у рядку. Кожен з цих рядків містить два числа: P_i (1 ≤ P_i ≤ N) і T_i (0 ≤ T_i ≤ 100). P_i – номер батьківського прилада (тобто прилада, для якого пристрій з номером i є підлеглим).
Вихідні дані
Виведіть у вихідний файл одне шукане число в процентах з точністю не менше 4 знаків після коми.