问题1822--凯文的交际网络

1822: 凯文的交际网络

时间限制: 1 Sec  内存限制: 128 MB
提交: 4  解决: 1
[提交] [状态] [讨论版] [命题人:]

题目描述

凯文正在某个社区发展他的关系网。不幸的是，他还没有和任何人联系。但他发现了N个潜
在的有价值的关系，编号从1到N。他决心与他们联系起来。
然而，在这个社区里，很少有人愿意成为外部人的朋友。N个人中的每个人和外部人建立联
系的标准是不同的，愿意和凯文交朋友情况是：如果他在社区已经有了Ai个朋友，或者如果
凯文给这个人Bi的费用。
你的工作是帮助凯文用最少的费用和N个人成朋友。

输入

第一行包含整数 N。接下来的 行每行包含两个整数 Ai和 Bi。

输出

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

样例输入

4 
3 3 
1 2 
0 5 
3 4

样例输出

3

提示

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

对于前 15 分，所有的Bi 都等于 1；
对于另外的30  分，N<=10；
对于另外的 30 分，N<=1000；
对于全部的数据，1<=N<=200000，1<=i<=N,0<=Ai<=N,0<=Bi<=10000。

来源/分类

 

[提交] [状态]