Debt Settlement in Wonseop City

Time limit1sMemory limit128 MB

Summary

Given a functional graph where each citizen owes money to exactly one creditor, find the minimum total money injected so all debts can be paid via chains of repayments.

Level: Medium6 of 10
Topics: Graph, Greedy, DFS
Solved: No attempts yet

Problem

Wonseop City has N citizens. Each citizen borrowed money from exactly one other citizen. For citizen i, A_i is the citizen who lent money to i, and B_i is the amount that citizen i must repay.

The city wants every debt to be repaid, but no citizen currently has any money. The city may give money to any subset of citizens. Once a citizen has at least the amount they owe, that citizen can repay their creditor. The creditor may then use the received money to repay their own debt later. If a citizen has money left after repaying their debt, they keep the remainder.

Given all debt relationships, compute the minimum total amount of money the city must give to citizens so that every debt can eventually be repaid.

Input

The first line contains the number of citizens N (2 <= N <= 200,000). Citizens are numbered from 1 to N.

Each of the next N lines contains two integers A_i and B_i. A_i is the number of the citizen who lent money to citizen i, and B_i is the amount citizen i must repay (1 <= A_i <= N, A_i != i, 1 <= B_i <= 10,000).

Output

Print the minimum total amount of money needed to settle all citizens' debts.

Examples3

Example 1
Input
```
4
2 100
1 100
4 70
3 70
```
Expected output
```
170
```
Example 2
Input
```
3
2 120
3 50
2 80
```
Expected output
```
150
```
Example 3
Input
```
5
3 30
3 20
4 100
5 40
3 60
```
Expected output
```
110
```