Debt Settlement in a Cyclic Town

In a town, there are \( n \) residents. Each resident has borrowed money exactly from one other resident. That is, for each resident \( i \) (\( 1 \le i \le n \)), they have borrowed an amount \( d_i \) from another resident \( p_i \) (with \( p_i \ne i \)).

At the time of repayment, every resident has spent all of their money so no one can directly settle their debt. In order to settle all debts and avoid conflicts, the mayor decides to provide some residents with money. When a resident receives money from the mayor, they immediately use it to pay the debt they owe. Upon receiving the payment, the creditor in turn uses that money to pay his own debt if possible, and so on. Note that:

• If a resident does not have enough money to fully pay their debt, they will hold on to the money until they have accumulated enough.
• If after paying the debt the resident has extra money, they keep the remaining amount.

For example, if resident A receives money from the mayor and uses it to pay the debt to B, then B can immediately pay his debt to C, and so on. In another example, if two residents mutually owe each other \(100\) dollars, the mayor only needs to give \(100\) dollars to one of them to cancel out both debts.

Your task is to calculate the minimum total amount of money the mayor must distribute in order to settle all the debts.

Observation: Since each resident borrows from exactly one other, the debt relationships form a functional graph in which every connected component contains exactly one cycle. The optimal strategy is to inject money into each cycle only. For a cycle containing residents \( i_1, i_2, \ldots, i_k \) with corresponding debts \( d_{i_1}, d_{i_2}, \ldots, d_{i_k} \), the minimum amount needed to settle the debts in that cycle is \( \min\{ d_{i_1}, d_{i_2}, \ldots, d_{i_k} \} \).

The answer is the sum of these minimum amounts over all cycles.

inputFormat

The first line of input contains an integer \( n \) (\( 2 \le n \le 10^5 \)) representing the number of residents.

Then \( n \) lines follow. The \( i \)-th line (1-indexed) contains two integers \( p_i \) and \( d_i \) where \( p_i \) (\( 1 \le p_i \le n,\ p_i \ne i \)) is the resident from whom resident \( i \) borrowed money, and \( d_i \) (\( 1 \le d_i \le 10^9 \)) is the amount of money borrowed.

outputFormat

Output a single integer: the minimum total amount of money the mayor needs to distribute in order to settle all debts.

sample

2
2 100
1 100

100