In a little town called Križ live \(N\) people. Each of them has borrowed some money from exactly one other inhabitant. Now the time has come to pay back all the debts, but the problem is that everybody has spent all of their money!

The mayor of Križ has decided to solve this problem. The town will give money to a few people so that they can pay back their debts. When some people get their money back, a chain reaction is started — for example: person \(A\) gets money from the city. Person \(A\) uses that money to pay the debt toward person \(B\). Person \(B\) then uses that money to pay the debt towards person \(C\), etc. If person \(B\) didn't have enough money to pay back the debt, they wait until they get enough. If they have more than enough money, person \(B\) will keep what is left after payback.

Another example: if two people live in Križ, and they owe \$$ 100$ to each other, the town will give \ $$100$ to one of them so they can pay back the debt to the other one.

Your task is to calculate the minimum total amount of money the town has to give to some subset of the inhabitants so that after the payback protocol described above all debts are paid.

The first line of input contains one integer \(N\) (\(2 \le N \le 200\,000\)), the number of inhabitants of Križ. They are numbered from \(1\) to \(N\).

The following \(N\) lines contain two integers, separated by a space. In the \(i\)-th of those lines, the first number \(A_i\) represents the id of the person the \(i\)-th person owes money to (\(1 \le A_i \le N\), \(A_i \ne i\)), and the second \(B_i\) represents the amount of the debt in dollars (\(1 \le B_i \le 10\,000\)).

First and only line of output should contain one integ\(er - th\)e minimum total ammount of money town
has to give to its inhabitants so all debts are returned.

riseoj 작성

출처 COCI 2010/2011 Contest 4