You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

AzusaCat 正在训练一个奇怪的神经网络。。。

题目描述

现在有 $n$ 个神经元，每个神经元 $i$ 接受输入电信号，当输入的电信号之和大于等于 $A_i$ 时，该神经元被激活并输出 $A_i$ 的电信号到另一个神经元 $to_i$。

每个神经元恰好有一个输出对象，AzusaCat 希望这个神经网络能先跑起来，请你帮他设计方案，给一部分神经元输入电信号使得所有神经元都被激活，在此条件下使得输入信号量总和最小。

输入格式

第一行一个整数 $n$ 表示神经元的个数。

接下来 $n$ 行，每行两个整数 $to_i, A_i$。

输出格式

一行一个整数表示答案。

5
5 9
3 9
5 6
2 7
3 3

18

10
4 3
4 3
2 9
10 2
2 7
1 8
1 10
10 4
2 4
6 8

36

20
8 65
3 87
7 16
13 59
1 45
8 13
2 91
10 19
10 83
17 72
10 61
10 16
5 31
17 54
16 57
15 53
6 74
11 9
13 25
13 71

551

提示

对于 $20\%$ 的数据满足 $n \le 20$

对于 $40\%$ 的数据满足 $n \le 300$

对于 $60\%$ 的数据满足 $n \le 5000$

对于 $100\%$ 的数据满足 $2\le n \le 2\times 10^5$, $1 \le to_i \ne i \le n$, $1 \le A_i \le 10^4$