The JOI Islands are a small island nation in the Pacific Ocean. There are $N$ islands in the JOI Islands, numbered from $1$ to $N$.

Communication between islands in the JOI Islands is mainly conducted via radio. Each island has one radio transmitter and one receiver. A transmitter can send radio waves in all directions, but a receiver can only receive radio waves from a specific direction. Therefore, each receiver can only receive radio waves from one specific island. However, by changing the orientation of a receiver, one can change which island's radio waves it can receive.

Currently, the receiver on island $i$ ($1 \le i \le N$) can receive radio waves from island $A_i$ ($A_i \neq i$). The cost to change the orientation of the receiver on island $i$ is $C_i$, regardless of how the orientation is changed.

The JOI Islands provide a telegraph service as a public utility. If the receiver on island $j$ ($1 \le j \le N, j \neq i$) can receive radio waves from island $i$ ($1 \le i \le N$), a telegram can be sent from island $i$ to island $j$ via radio communication. Telegrams may also be sent via several intermediate islands. That is, for islands $i, j, k$ ($1 \le i, j, k \le N$ and $i, j, k$ are all distinct), if a telegram can be sent from island $i$ to island $j$, and a telegram can be sent from island $j$ to island $k$, then a telegram can be sent from island $i$ to island $k$. Telegrams cannot be sent by any method other than radio communication.

As the Minister of Communications of the JOI Islands, you want to ensure that a telegram can be sent from any island to any other island. To achieve this, it may be necessary to change the orientation of the receivers on some islands. The cost of changing the orientation of the receivers on several islands is the sum of the costs of changing the orientation of each receiver.

Calculate the minimum cost required to ensure that a telegram can be sent from any island to any other island.

Input

Read the following data from standard input:

• The first line contains an integer $N$, representing that there are $N$ islands in the JOI Islands.
• The $i$-th line of the following $N$ lines ($1 \le i \le N$) contains integers $A_i$ and $C_i$ separated by a space, representing that the receiver on island $i$ can currently receive radio waves from island $A_i$, and the cost to change its orientation is $C_i$.

Output

Output the minimum cost required to ensure that a telegram can be sent from any island to any other island on a single line.

Constraints

All input data satisfies the following conditions:

• $2 \le N \le 100\,000$.
• $1 \le A_i \le N$ ($1 \le i \le N$).
• $A_i \neq i$ ($1 \le i \le N$).
• $1 \le C_i \le 1\,000\,000\,000$ ($1 \le i \le N$).

Subtasks

1. (10 points) $N \le 10$ is satisfied.
2. (30 points) $N \le 15$ is satisfied.
3. (30 points) $N \le 3\,000$ is satisfied.
4. (30 points) No additional constraints.

Examples

Input 1

4
2 2
1 4
1 3
3 1

Output 1

4

Note 1

Change the orientation of the receiver on island 2 to receive radio waves from island 4. Then, a telegram can be sent from any island to any other island, and the cost incurred is 4. Since the cost cannot be less than 4 no matter how the receiver orientations are changed, output 4.

Input 2

4
2 2
1 6
1 3
3 1

Output 2

5

Note 2

First, change the orientation of the receiver on island 1 to receive radio waves from island 4. Next, change the orientation of the receiver on island 3 to receive radio waves from island 2. Then, a telegram can be sent from any island to any other island, and the cost incurred is $2 + 3 = 5$. Since the cost cannot be less than 5 no matter how the receiver orientations are changed, output 5.

Input 3

4
2 2
1 3
4 2
3 3

Output 3

4

Note 3

It is sufficient to change the orientation of the receivers on island 1 and island 3.

Input 4

3
2 1
3 1
1 1

Output 4

0

Note 4

It is not necessary to change the orientation of any island's receiver.