Many centuries ago Martians switched to using huge robots for military operations. During the current Moon conquest campaign, all of the Martian army is located at the headquarters on Mars, and each person is controlling the actions of his robot. There is a strict hierarchy in the Martian army: each person excepting the general (there is only one general in the army) has a direct commander. According to the army regulations, communication is allowed only between a commander and his direct subordinate. The communication is carried out via the headquarters local network. At the headquarters, each military person has his own computer, and computers are numbered from 1 to N, where N is the size of the Martian army. It is a tradition that a subordinate's computer has number that is greater than the number of his commander's computer. Each military person, in addition to the number of his computer, is characterized by his reliability. This is a real number; the owner of the computer i has reliability A_i. The general has reliability 1, and soldiers (soldiers and only they have no subordinates) have reliability 0.

The traffic in the headquarters network is not free for the military. For every megabyte of traffic between the ith computer and the computer of the commander of the ith computer's owner, the central Martian provider demands C_i Martian dollars in payment. The complication is that the volume of traffic between any two headquarters computers is a state secret, and is unknown even to the provider. Every month the provider sends a bill, and the military write there the traffic (a whole number of megabytes) themselves. Let a commander and his subordinate have computers with numbers i and k respectively. According to the contract with the provider, the traffic between the computers i and k must be not less than A_i–A_k. In the beginning of every month, the provider's representatives know the hierarchy in the Martian army and costs of a megabyte of traffic, but they don't know the numbers A_i except for the general and soldiers, and of course they don't know beforehand the amounts of traffic that the military will write in the bill. It is interesting to know the guaranteed amount of money that the provider will receive from the military.

The first line contains the size of the army 2 ≤ N ≤ 100000. Each of the next N–1 lines contains integers K_i and C_i, which are the number of the computer of the commander of the ith computer's owner and the cost of a megabyte of traffic between the computers i and K_i (1 ≤ K_i < i ≤ N, 0 ≤ C_i ≤ 1000).

Output the minimal guaranteed amount of payment to the provider in Martian dollars. This amount must be a real number given with exactly two decimal digits.