Island

Problem Source

IOI 2008

Problem Description

You are going to tour a park consisting of $N$ islands. The local administration has built from each island $i$ a bridge of length $L_i$ to another island, though the bridge can be walked in both directions. In addition, for every pair of islands there is a dedicated ferry running between the two. Compared to taking a ferry, you prefer walking. You want the total length of bridges you walk to be as large as possible, subject to the following restrictions:

• You may freely choose an island to start the tour.
• No island may be visited more than once.
• At any time, from your current island $S$ you may go to another not-yet-visited island $D$ by either:
  • Walking: only possible when there is a bridge between $S$ and $D$. In this case, the bridge's length is added to your total walking distance.
  • Ferry: you may choose this option only when there is no combination of bridges and previously used ferries that can take you from $S$ to $D$ (when checking reachability, you should consider all paths, including those through islands you have already visited).

Note that you do not have to visit all islands, and you may not be able to walk all the bridges.

Write a program that, given the $N$ bridges and their lengths, computes the maximum sum of bridge lengths you can walk under the rules above.

Input Format

The first line contains one integer $N$ ($2 \leq N \leq 10^6$), the number of islands in the park.

Then $N$ lines follow, each describing one island. The $i$-th line contains two integers separated by a single space, describing the bridge built from island $i$. The first integer is the island at the other end of the bridge, and the second integer is the bridge's length $L_i$ ($1 \leq L_i \leq 10^8$). You may assume that for every bridge its endpoints are always on different islands.

Output Format

Output a single integer: the maximum possible walking distance.

Sample Input

7
3 8
7 2
4 2
1 4
1 9
3 4
2 3

Sample Output

24

Sample Explanation

The sample has $N = 7$ bridges, namely $(1-3), (2-7), (3-4), (4-1), (5-1), (6-3)$ and $(7-2)$. Note that two different bridges connect islands $2$ and $7$.

One way to achieve the maximum walking distance is:

• Start at island $5$.
• Walk the bridge of length $9$ to island $1$.
• Walk the bridge of length $8$ to island $3$.
• Walk the bridge of length $4$ to island $6$.
• Take the ferry from island $6$ to island $7$.
• Walk the bridge of length $3$ to island $2$.

Finally you arrive at island $2$, and your total walking distance is $9 + 8 + 4 + 3 = 24$.

Only island $4$ is not visited. Note that at the end of the tour above you cannot visit this island. More precisely:

• You cannot walk there, because there is no bridge connecting island $2$ (your current island) and island $4$.
• You cannot take a ferry there, because you can already reach island $4$ from your current island $2$. One such way: walk the $(2-7)$ bridge, then take the ferry you already used from island $7$ to island $6$, then walk the $(6-3)$ bridge, and finally walk the $(3-4)$ bridge.