You are visiting a park which has N islands. From each island i, exactly one bridge was constructed. The length of that bridge is denoted by Li. The total number of bridges in the island is N. Each bridge can be traversed in both directions. Also, for each pair of island, there is a unique ferry that travels back and forth between them.

Since you like walking better than riding ferries, you want to maximize the sum of the lengths of the bridges you cross subject to the constraints below :

• You can start a visit on an island of your choice.
• You may not visit any island more than once.
• At any time you may move from your current island S to any island D which you have not visited before. You can go from S to D either by walking, in which case the length of the bridge you take will be added to the total length or by ferry if the islands are not connected by any bridge (when checking for connectivity you should include those islands which have been previously visited by you).

Note that you do not have to visit all the islands, and it may be impossible to cross al the bridges.

Given N bridges along with their lengths, your task is to find out the maximum distance you can walk by following the rules above.

Constraints :

2 <= N <= 100000

1 <= Li <= 1000000

Input

The first line of the input contains N, the number of islands. Islands are numbered 1 to N inclusive. Then follow N lines. The ith of these lines contains two integers Ii and Li, which are the island the ith island connects to and the length of the bridge respectively. You may assume that each bridge has two different islands as its endpoints.

Output

You must write a single line which is the maximum possible distance that you can walk.

Example

Input :

7

3 8

7 2

4 2

1 4

1 9

3 4

2 3

Output :

24

Explanation of the example :

Start at 5.

Walk to 1.

Walk to 3.

Walk to 6.

Ferry to 7.

Walk to 2.

Hence total distance you walked is 9 + 8 + 4 + 3 = 24.

Note : The final answer fits within 64 bit integer.