在一个名叫 Križ 的小镇上住着 $N$ 个人。他们每个人都恰好向另外一个人借了钱。现在到了偿还所有债务的时候，但问题是每个人都把钱花光了！

Križ 的镇长决定解决这个问题。小镇将给一些人一些钱，以便他们能够偿还债务。当某些人拿到钱（或被还钱）后，会引发连锁反应——例如：人 A 从城市（镇政府）那里得到了钱。人 A 用这笔钱向人 B 偿还债务。然后人 B 用这笔钱向人 C 偿还债务，依此类推。如果人 B 没有足够的钱来偿还债务，他们会等待直到攒够。如果他们有比债务更多的钱，人 B 将在偿还后保留剩余的钱。

另一个例子：如果 Križ 住着两个人，他们互相欠对方 $100$ 元，小镇将给其中一个人 $100$ 元，这样他就可以向另一个人偿还债务（另一个人收到 $100$ 元后，又可以用这 $100$ 元还给第一个人）。

你的任务是计算小镇必须给居民子集的最小资金总额，以便在上述还款协议后，所有债务都得到偿还。

输入格式

输入的第一行包含一个整数 $N$ ($2 \le N \le 200\,000$)，表示 Križ 的居民人数。他们从 $1$ 到 $N$ 进行编号。

接下来的 $N$ 行，每行包含两个由空格隔开的整数。在第 $i$ 行中，第一个数 $A_i$ 表示第 $i$ 个人欠钱的对象编号 ($1 \le A_i \le N, A_i \ne i$)，第二个数 $B_i$ 表示欠款金额（单位为元，$1 \le B_i \le 10\,000$）。

输出格式

输出的唯一一行应包含一个整数，表示小镇必须给其居民的最小资金总额，以使所有债务都得到偿还。

样例

输入样例 1

4
2 100
1 100
4 70
3 70

输出样例 1

170

输入样例 2

3
2 120
3 50
2 80

输出样例 2

150

输入样例 3

5
3 30
3 20
4 100
5 40
3 60

输出样例 3

110