Telegraph (Translated)

JOI Spring Training Camp 2015/16
Original Statement / Submission Site

Problem Statement

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

Communication between the islands is conducted mainly by radio. Each island has one transmitter and one receiver. A transmitter can send radio waves in every direction, but a receiver can receive radio waves only from a particular direction. Therefore, each receiver can currently receive radio waves from exactly one particular island. By changing the direction of a receiver, however, the island from which it receives radio waves can be changed.

Currently, the receiver on island i can receive radio waves from island A_i, where A_i ≠ i. Changing the direction of the receiver on island i costs C_i, regardless of the new direction.

The JOI Islands operate a public telegraph service. If the receiver on island j can receive radio waves from island i, then a telegraph can be sent from island i to island j.

A telegraph may also be relayed through several islands. For example, if a telegraph can be sent from island i to island j, and from island j to island k, then it can also be sent from island i to island k. Telegraphs cannot be sent by any method other than radio communication.

As the Minister of Communications of the JOI Islands, you want to make it possible to send a telegraph from any island to any other island. To achieve this, it may be necessary to change the directions of some receivers. The total cost is the sum of the costs of all receivers whose directions are changed.

Task

Given the number of islands and the current receiver information for every island, compute the minimum total cost required to make it possible to send a telegraph from any island to any other island.

Input

The input is given as follows:

• The first line contains an integer N, the number of islands.
• Each of the next N lines contains two integers A_i and C_i. The receiver on island i currently receives radio waves from island A_i, and changing its direction costs C_i.

Output

Output one integer: the minimum total cost required to make it possible to send a telegraph from any island to any other island.

Constraints

• 2 ≤ N ≤ 100,000
• 1 ≤ A_i ≤ N
• A_i ≠ i
• 1 ≤ C_i ≤ 1,000,000,000

Subtasks

• Subtask 1 [10 points]: N ≤ 10.
• Subtask 2 [30 points]: N ≤ 15.
• Subtask 3 [30 points]: N ≤ 3,000.
• Subtask 4 [30 points]: No additional constraints.

Sample Input 1

4
2 2
1 4
1 3
3 1

Sample Output 1

4

Explanation of Sample Output 1

Change the direction of the receiver on island 2 so that it can receive radio waves from island 4. Then a telegraph can be sent from any island to any other island, and the total cost is 4.

No arrangement of receiver directions can achieve this with a cost less than 4, so the answer is 4.

Sample Input 2

4
2 2
1 6
1 3
3 1

Sample Output 2

5

Explanation of Sample Output 2

First, change the receiver on island 1 so that it can receive radio waves from island 4. Next, change the receiver on island 3 so that it can receive radio waves from island 2.

Then a telegraph can be sent from any island to any other island, and the total cost is 2 + 3 = 5. No smaller cost is possible, so the answer is 5.

Sample Input 3

4
2 2
1 3
4 2
3 3

Sample Output 3

4

It is sufficient to change the directions of the receivers on islands 1 and 3.

Sample Input 4

3
2 1
3 1
1 1

Sample Output 4

0

No receiver direction needs to be changed.