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 ≤ pi ≤ n; 0 ≤ ti ≤ 100).
Output the maximal possible value of x with absolute error at most 10−4.
Problem Author: Kirill Butin
Problem Source: XII USU Open Personal Contest (March 19, 2011)