Hide

Dugovi

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 major 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.

Output

The first and only line of output should contain one integer – the minimum total ammount of money town has to give to its inhabitants so all debts are returned.

Sample Input 1 Sample Output 1
4
2 100
1 100
4 70
3 70

170

Sample Input 2 Sample Output 2
3
2 120
3 50
2 80

150

Sample Input 3 Sample Output 3
5
3 30
3 20
4 100
5 40
3 60

110

CPU Time limit 1 second
Memory limit 1024 MB
Difficulty 6.7hard
Statistics Show