题目描述

在一个小镇上有 $n$ 位居民，每位居民都恰好从其他一位居民那里借了一些钱。

现在到了还债的时间。但问题是每个人都把自己的钱用完了；也就是说任何人都无力偿还债务。这样以来产生了很多冲突。

市长决定解决这个问题。他预想要给一部分居民一些钱，以便于他们用来还债。不过当一部分居民拿到了钱，一系列的连锁反应就开始了。

例如， $A$ 从市长那里得到了钱。$A$ 赶忙用这些钱偿还 $B$ 的债务。$B$ 也正好偿还 $C$ 的债务，以此类推。

其中，如果 $B$ 没有足够的钱来一次还清，那么他会把钱暂时留在自己手里等到钱够了；如果还完债后还有剩余， $B$ 也会自己留着。（$B$ 的行为对于任意一个人适用）

另一个例子：如果两个镇上的居民互欠对方 $100$ 美元，那么市长只需要给其中一个人 $100$ 美元，这两个债务就都解决了。

你需要通过程序来计算出：市长至少要支出多少元给一部分居民才能平息一切债务？

输入格式

输入一行一个整数 $n$，表示镇上居民的数量。

接下来的 $n$ 行，每行两个整数 $A_i,B_i$，表示第 $i$ 个人欠第 $A_i$ 个人 $B_i$ 美元。

居民从 $1\sim n$ 编号。

输出格式

输出一行一个整数，表示市长最少支出的金额。

4
2 100
1 100
4 70
3 70

170

3
2 120
3 50
2 80

150

5
3 30
3 20
4 100
5 40
3 60

110

提示

数据规模与约定

对于 $100\%$ 的数据，保证 $2\le n\le 2\times 10^5$，$1\le A_i\le n$ 且 $A_i\neq i$，$1\le B_i\le 10^4$。

说明

题目译自 COCI2010-2011 CONTEST #4 T5 DUGOVI。