题目描述

译自 CCO 2017 Day2 「Professional Network」

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

数据范围与提示

对于前 $15$ 分，所有的 $B_i$ 都等于 $1$；
对于另外的 $30$ 分，$N\leqslant 10$；
对于另外的 $30$ 分，$N\leqslant 1000$；
对于全部的数据，$1\leqslant N \leqslant 200\, 000$，$1\leqslant i\leqslant N;\ 0\leqslant A_i\leqslant N;\ 0\leqslant B_i\leqslant 10\, 000$。
请注意在 LibreOJ 上共有 $5$ 个子任务，其中第一个子任务为样例。