Islands#275

Islands

5 seconds

256 megabytes

Hard

You are visiting a park that contains $N$ islands. From each island $i$ , exactly one bridge has been constructed. The length of the bridge from island $i$ is denoted by $L_{i}$ L_i. The total number of bridges in the park is $N$ . Although each bridge was built to connect two islands, now each bridge can be traversed in both directions. In addition, for each pair of islands, there is a unique ferry running between them in both directions.

Since you prefer walking to taking the ferry, you want to maximize the sum of the lengths of the bridges you cross, subject to the rules below.

You can start your walk from any 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 another island $D$ that you have not yet visited. You can move from $S$ to $D$ in the following ways:
1. Walking: This is only possible if there is a bridge between the two islands. In this case, the length of the bridge is added to your walking total.
2. Ferry: You can use the ferry only if it is not possible to get from $S$ to $D$ using any combination of bridges and/or previously used ferries, even by passing through islands you have already visited. Note that you do not have to visit all islands, and it may not be possible to cross all bridges.

Given the $N$ bridges and their lengths, write a program that calculates the maximum total walking distance you can achieve, following the rules above.

2 \leq N \leq 1000000

2 \leq N \leq 1\,000\,000

1 \leq L_{i} \leq 100000000

1 \leq L_i \leq 100\,000\,000

Input

Your program should read from standard input:

The first line contains the integer $N$ — the number of islands in the park. Islands are numbered from $1$ to $N$ .
The next $N$ lines each describe a bridge. The $i$ -th of these lines describes the bridge from island $i$ with two space-separated integers: the first integer is the index of the other island the bridge connects to, and the second integer is $L_{i}$ L_i, the length of the bridge. The endpoints of each bridge are always two different islands.

Output

Output a single integer — the maximum possible total walking distance.

Examples

Example 1

Note

Note 1. For some test cases, the answer may not fit in a $32$ -bit integer. Use $in t 64$ in Pascal or $l o n g l o n g$ long~long in C/C++ to get full points for this problem.

Note 2. In the contest environment, $64$ -bit integer types are read much more slowly in Pascal than $32$ -bit types, even if the value fits in $32$ bits. It is recommended to use $32$ -bit types for reading input. For some cases worth $40$ points, $N$ does not exceed $4000$ .