ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Open Personal Contest 2011

About     Problems     Submit solution     Judge status     Standings
Contest is over

C. Hugo II's War

Time limit: 0.5 second
Memory limit: 64 MB
The glorious King Hugo II has declared a war—a war that is holy, victorious, almost bloodless, but ruinous!
Right after declaring the war the king has started summoning the army. He plans to send a recruitment order to all his immediate vassals, who will send the order to their vassals, and so on. In the end, every nobleman of the kingdom will be involved in the preparation for the war.
As soon as a nobleman who has no vassals receives the order, he immediately begins recruiting soldiers and joins his overlord in a few days. If a nobleman has vassals, he waits until there are at least x% of his immediate vassals ready for the war, then summons his own troops and also joins his overlord. The glorious King Hugo II will go the war as soon as at least x% of his immediate vassals are ready.
King Hugo II wants to state the number x in his recruitment order. The king needs as many soldiers as possible for his military campaign. However, if the recruitment takes more than t days, the enemy may learn about the imminent intrusion and strike first. Help Hugo II find the maximal possible value of x.


The first line contains the number n of noblemen in the kingdom and the maximal number of days t that can be spent for summoning the army (1 ≤ n ≤ 104; 0 ≤ t ≤ 106). The noblemen are numbered from 1 to n. King Hugo II has number 1, and the noblemen with numbers from 2 to n are described in the following n − 1 lines. The i-th of these lines describes the nobleman with number i and contains integers pi and ti, where pi is the number of his overlord and ti is the number of days the i-th nobleman will need to summon his troops (1 ≤ pin; 0 ≤ ti ≤ 100).


Output the maximal possible value of x with absolute error at most 10−4.


6 3
1 2
2 2
2 1
1 2
1 4
Problem Author: Kirill Butin
Problem Source: XII USU Open Personal Contest (March 19, 2011)
To submit the solution for this problem go to the Problem set: 1822. Hugo II's War