Device Survey
There are N devices, each potentially connected to several subordinate devices via cables. These devices are uniquely numbered from 1 to N, forming a tree structure with device number 1 as the root.
The system processes queries in the following manner: the root device sends a request to all its direct subordinates simultaneously. Each subordinate then forwards the request to its own subordinates, continuing this process throughout the tree.
Each device has a specific processing time, denoted as T_i milliseconds.
The data processing for each device is as follows:
If a device has no subordinates, it returns its status after T_i milliseconds to the device from which it received the request.
If a device has subordinates, it begins processing as soon as it receives data from at least X% of its immediate subordinates, and then returns the results after T_i milliseconds.
Your task is to determine the maximum value of X such that the entire query process is completed within a time not exceeding T milliseconds.
The query is considered complete when the root device has gathered all the necessary information. The time taken for information transmission between devices is negligible, and the processing time of the root device itself is not included.
Input
The first line of the input contains two integers: N (1 ≤ N ≤ 10,000) and T (0 ≤ T ≤ 10^6).
The following (N – 1) lines provide details about devices numbered from 2 to N. Each line contains two integers: P_i (1 ≤ P_i ≤ N) and T_i (0 ≤ T_i ≤ 100). Here, P_i is the parent device number, indicating that device i is a subordinate of device P_i.
Output
Output the maximum percentage X with a precision of at least 4 decimal places.