Zerg has n(1≤n≤5000) bases and n-1 roads make up a tree. Let f(x) =max{time needed for a zergling to run from base x to another base y } (y≠x).A formula can evaluate the traffic efficiency is g=∑1-n f(x). The less the value of g is, the better the traffic efficiency will be. A pair of Nydus Canals can be built only at both ends of a road so that if a zergling arrive at an end then they can be transferred to the other end immediately, and the speed of the zergling will be twice as fast as before . Now they can build at most one pair of Nydus Canals to make the value of g as small as possible.

You should pay attention that once a zergling pass the Nydus Canals, it can’t go back through the Nydus Canals again.It needs no time for a zergling to run through a base.

The input consists of several test cases. Each test case starts with the number of bases n(1≤n≤5000). Then n-1 lines follow, describing the roads .In these n-1 lines ,the i -th line contains 2 integers  f_(i+1) (1≤f_(i+1)≤5000) and〖 w〗_(i+1) (1≤w_(i+1)≤200000 can be divided by 2)— means there exists an road connecting the (i+1)-th base and the f_(i+1)-th base directly , and it takes w_(i+1)minutes for a zergling to run through the road (if the zergling haven’t passed through Nydus Canals).

For each test case ,output the minimum value of g .

2
1 4
4
1 2
2 2
3 4

0
12