Device Survey#2001
There are devices, each potentially connected to several subordinate devices via cables. These devices are uniquely numbered from to , forming a tree structure with device number 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, and this process continues throughout the tree.
Each device has a specific processing time, denoted as T_i milliseconds.
The data processing for each device occurs 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.
Otherwise, it begins processing as soon as it receives data from at least % of its immediate subordinates, and then returns the results after T_i milliseconds.
Determine the maximum value of such that the entire query process is completed within a time not exceeding 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.
The first line of the input contains two integers: (1 \leq N \leq 10000) and (0 \leq T \leq 10^6).
The following (N-1) lines provide details about devices numbered from to . Each line contains two integers: P_i (1 \leq P_i \leq N) and T_i (0 \leq T_i \leq 100). Here, P_i is the parent device number, indicating that device is a subordinate of device P_i.
Output the maximum percentage with a precision of at least decimal places.
Example 1