JOI 君有 $N$ 个用于连接手机的挂绳。挂绳编号为 $1$ 到 $N$。JOI 君打算将其中一些挂绳连接到手机上。

JOI 君拥有的挂绳有些特殊，部分挂绳上带有若干个用于连接其他挂绳的端子。每根挂绳既可以直接连接到手机上，也可以连接到其他挂绳的端子上。直接连接到手机上的挂绳最多只能有一根。

此外，每根挂绳在连接后都有一个对应的“喜悦值”。这个喜悦值用一个整数表示。有些挂绳是 JOI 君不喜欢的，这种情况下喜悦值为负数。

JOI 君希望最大化连接到手机上的所有挂绳的喜悦值总和。注意，并不一定要将所有端子都连接上挂绳，也可以一根挂绳都不连接。

题目描述

给定 JOI 君拥有的 $N$ 根挂绳的信息。请编写一个程序，求出在合理连接挂绳的情况下，连接到手机上的挂绳的喜悦值总和的最大值。

输入格式

从标准输入读取以下数据：

• 第 $1$ 行包含一个整数 $N$，表示挂绳的数量。
• 接下来的 $N$ 行中，第 $i$ 行 ($1 \le i \le N$) 包含两个以空格分隔的整数 $A_i$ 和 $B_i$。这表示挂绳 $i$ 有 $A_i$ 个端子，且连接该挂绳所获得的喜悦值为 $B_i$。

输出格式

将连接到手机上的挂绳的喜悦值总和的最大值作为一个整数，输出到标准输出中。

数据范围

所有输入数据满足以下条件：

• $1 \le N \le 2000$
• $0 \le A_i \le N$ ($1 \le i \le N$)
• $-1\,000\,000 \le B_i \le 1\,000\,000$ ($1 \le i \le N$)

子任务

• 子任务 1 [5 点]：满足 $N \le 15$。
• 子任务 2 [5 点]：满足 $B_i \ge 0$ ($1 \le i \le N$)。
• 子任务 3 [45 点]：满足 $A_i \le 15$ ($1 \le i \le N$)。
• 子任务 4 [45 点]：无附加限制。

样例

样例输入 1

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

样例输出 1

5

说明 1

对于该输入，按以下方式连接挂绳可使喜悦值总和达到最大值 $5$： 将挂绳 $2$ 直接连接到手机上。 将挂绳 $1$ 连接到挂绳 $2$ 的端子上。 * 将挂绳 $5$ 连接到挂绳 $2$ 的端子上。

样例输入 2

6
2 -3
3 -1
0 -4
0 -2
1 -3
4 -1

样例输出 2

0

说明 2

对于该输入，所有挂绳的喜悦值均小于 $0$。因此，不连接任何挂绳时喜悦值总和最大。

样例输入 3

15
1 -4034
1 3406
0 6062
4 -6824
0 9798
0 4500
0 -1915
1 2137
0 9786
0 7330
0 -9365
2 2730
0 -5797
0 6129
0 8925

样例输出 3

43417