Corruption
The ministry, which issues licenses to work N officials (including ministers), and:
Each officer (except the Minister) has a superior;
Each officer has a 0 to 4 subordinate officials;
Chief of my chief, not my chief;
Slave of my slave, not my slave.
License signed by the Minister. To have the signature of any officer or minister, you need to bribe him to Dachi, after having received the signature of one of his subordinates, if any.
What is the minimum amount sufficient to obtain a license?
Input
The first line of the number N – the number of officials in the ministry. Next comes the N lines. In the і-th row (і = 1..N) recorded data on the і-th clerk in the following format: D[і] - sum of bribes, K[і] – the amount and number of his subordinates. The minister has the number one. All numbers are natural and do not exceed 100.
Output
The answer to the problem.