P6346 [CCO 2017] 专业网络

Kevin 正在一个社区中开发他的专业网络。不幸的是，他是个外地人，还不认识社区中的任何人。但是他可以与 $n$ 个人建立朋友关系 。 然而，社区里没几个人想与一个外地人交朋友。Kevin 想交朋友的 $n$ 个人都有类似但不同的与外地人交友的准则。在 Kevin 已经直接认识了社区中的 $a_i$ 个人后，第 $i$ 个人就愿意与 Kevin 交朋友了，否则 Kevin 就要付出 $b_i$ 的代价与他成为朋友。 你的任务是，使 Kevin 与这 $n$ 个人都交上朋友，并且最小化他付出的代价。

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

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

#### 样例解释 对于样例 $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](https://cemc.math.uwaterloo.ca/contests/computing/2017/) Day2「[Professional Network](https://cemc.math.uwaterloo.ca/contests/computing/2017/stage%202/day2.pdf)」。 说明：翻译来自 [LOJ](https://loj.ac/problem/2754)。