A6542. 「CCO 2017」专业网络
编程题
省选/NOI-
知识点
题目描述
**译自 [CCO 2017](https://cemc.math.uwaterloo.ca/contests/computing/past_ccc_contests/2017/index.html) Day2 「[Professional Network](https://cemc.math.uwaterloo.ca/contests/computing/past_ccc_contests/2017/stage%202/day2.pdf)」**
Kevin 正在一个社区中开发他的专业网络。不幸的是，他是个外地人，还不认识社区中的任何人。但是他可以与 $N$ 个人建立朋友关系 。
然而，社区里没几个人想与一个外地人交朋友。Kevin 想交朋友的 $N$ 个人都有类似但不同的与外地人交友的准则。在 Kevin 已经直接认识了社区中的 $A_i$ 个人后，第 $i$ 个人就愿意与 Kevin 交朋友了，否则 Kevin 就要付出 $B_i$ 的代价与他成为朋友。
你的任务是，使 Kevin 与这 $N$ 个人都交上朋友，并且最小化他付出的代价。
Kevin 正在一个社区中开发他的专业网络。不幸的是，他是个外地人，还不认识社区中的任何人。但是他可以与 $N$ 个人建立朋友关系 。
然而，社区里没几个人想与一个外地人交朋友。Kevin 想交朋友的 $N$ 个人都有类似但不同的与外地人交友的准则。在 Kevin 已经直接认识了社区中的 $A_i$ 个人后，第 $i$ 个人就愿意与 Kevin 交朋友了，否则 Kevin 就要付出 $B_i$ 的代价与他成为朋友。
你的任务是，使 Kevin 与这 $N$ 个人都交上朋友，并且最小化他付出的代价。
输入格式
第一行包含整数 $N$。接下来的 $N$ 行每行包含两个整数 $A_i$ 和 $B_i$。
输出格式
输出一行一个整数表示 Kevin 付出的最小代价。
输入输出样例
输入 #1
4 3 3 1 2 0 5 3 4
输出 #1
3
输入 #2
5 0 9 1 8 2 7 3 6 4 5
输出 #2
0
输入 #3
3 0 6 2 7 3 8
输出 #3
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$ 个子任务，其中第一个子任务为样例。**
对于另外的 $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$ 个子任务，其中第一个子任务为样例。**