题目描述

小 X 有 $N$ 个装在手机上的挂饰，编号为 $1,2,\dots,N$。小 X 可以将其中的一些装在手机上。

小 X 的挂饰有一些与众不同——其中的一些挂饰附有可以挂其他挂件的挂钩。每个挂件要么直接挂在手机上，要么挂在其他挂件的挂钩上。直接挂在手机上的挂件最多有 $1$ 个。

此外，每个挂件有一个安装时会获得的喜悦值，用一个整数来表示。如果小 X 很讨厌某个挂饰，那么这个挂饰的喜悦值就是一个负数。

小 X 想要最大化所有挂饰的喜悦值之和。注意不必要将所有的挂钩都挂上挂饰，而且一个都不挂也是可以的。

输入格式

第一行一个整数 $N$，代表挂饰的个数。

接下来 $N$ 行，第 $i$ 行（$1 \le i \le N$）有两个空格分隔的整数 $A_i$ 和 $B_i$，表示挂饰 $i$ 有 $A_i$ 个挂钩，安装后会获得 $B_i$ 的喜悦值。

输出格式

输出一行一个整数，表示手机上连接的挂饰喜悦值总和的最大值。

样例输入 1

5
0 4
2 -2
1 -1
0 1
0 3

样例输出 1

5

说明

其它样例说明

• 样例 $2$：见选手目录下的 strap/strap2.in 与 strap/strap2.ans，该测试用例满足测试点编号 $1\sim 4$ 的约束条件。
• 样例 $3$：见选手目录下的 strap/strap3.in 与 strap/strap3.ans，该测试用例满足测试点编号 $5\sim 8$ 的约束条件。
• 样例 $4$：见选手目录下的 strap/strap4.in 与 strap/strap4.ans，该测试用例满足测试点编号 $9\sim 12$ 的约束条件。
• 样例 $5$：见选手目录下的 strap/strap5.in 与 strap/strap5.ans，该测试用例满足测试点编号 $13\sim 16$ 的约束条件。
• 样例 $6$：见选手目录下的 strap/strap6.in 与 strap/strap6.ans，该测试用例满足测试点编号 $17\sim 20$ 的约束条件。

数据范围

• $1 \le N \le 2000$
• $0 \le A_i \le N$（$1 \le i \le N$）
• $-10^6 \le B_i \le 10^6$（$1 \le i \le N$）

各测试点的限制如下表所示：

点击下载大样例