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.

题目描述

Kevin 正在一个社区中开发他的专业网络。不幸的是，他是个外地人，还不认识社区中的任何人。但是他可以与 $n$ 个人建立朋友关系 。

然而，社区里没几个人想与一个外地人交朋友。Kevin 想交朋友的 $n$ 个人都有类似但不同的与外地人交友的准则。在 Kevin 已经直接认识了社区中的 $a_i$ 个人后，第 $i$ 个人就愿意与 Kevin 交朋友了，否则 Kevin 就要付出 $b_i$ 的代价与他成为朋友。

你的任务是，使 Kevin 与这 $n$ 个人都交上朋友，并且最小化他付出的代价。

输入格式

第一行包含一个整数 $n$。

接下来的 $n$ 行，每行包含两个整数 $a_i,b_i$。

输出格式

输出一行一个整数，表示 Kevin 付出的最小代价。

4
3 3
1 2
0 5
3 4

3

5
0 9
1 8
2 7
3 6
4 5

0

3
0 6
2 7
3 8

8

提示

样例解释

对于样例 $1$：Kevin 可以立即与 $3$ 号人成为朋友，因为已经建立了这个朋友关系，他也能与 $2$ 号人成为朋友。他需要付出 $3$ 的代价与 $1$ 号人成为朋友，这样他一共有 $3$ 个朋友，使得他能与 $4$ 号人成为朋友。

对于样例 $2$：Kevin 不用付出任何代价就能和所有人成为朋友。

对于样例 $3$：Kevin 应该立即与 $1$ 号人成为朋友，然后付出 $8$ 的代价与 $3$ 号人成为朋友， 最后与 $2$ 号人建立朋友关系。

数据范围及约定

本题采用多测试点捆绑测试，共有 $4$ 个子任务。

• Subtask 1（15 points）：所有的 $b_i$ 都等于 $1$；
• Subtask 2（30 points）：$1 \le n \le 10$；
• Subtask 3（30 points）：$1 \le n \le 10^3$。
• Subtask 4（25 points）：$1 \le n \le 2 \times 10^5$。

对于全部的测试点，保证 $1 \le n \le 2 \times 10^5$，$1 \le i \le n$，$0 \le a_i \le n$，$0 \le b_i \le 10^4$。

来源：CCO 2017 Day2「Professional Network」。

说明：翻译来自 LOJ。