#2754. 「CCO 2017」专业网络

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Mingqi_H

题目描述

译自 CCO 2017 Day2 「Professional Network

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

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

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

输入格式

第一行包含整数 NNN。接下来的 NNN 行每行包含两个整数 AiA_iAiBiB_iBi

输出格式

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

样例

样例输入 1

4
3 3
1 2
0 5
3 4

样例输出 1

3

样例 1 解释

Kevin 可以立即与 333 号人成为朋友,因为已经建立了这个朋友关系,他也能与 222 号人成为朋友。他需要付出 333 的代价与 111 号人成为朋友,这样他一共有 333 个朋友,使得他能与 444 号人成为朋友。

样例输入 2

5
0 9
1 8
2 7
3 6
4 5

样例输出 2

0

样例 2 解释

Kevin 不用付出任何代价就能和所有人成为朋友。

样例输入 3

3
0 6
2 7
3 8

样例输出 3

8

样例 3 解释

Kevin 应该立即与 111 号人成为朋友,然后付出 888 的代价与 333 号人成为朋友, 最后与 222 号人建立朋友关系。

数据范围与提示

对于前 151515 分,所有的 BiB_iBi 都等于 111
对于另外的 303030 分,N⩽10N\leqslant 10N10
对于另外的 303030 分,N⩽1000N\leqslant 1000N1000
对于全部的数据,1⩽N⩽2000001\leqslant N \leqslant 200\, 0001N2000001⩽i⩽N; 0⩽Ai⩽N; 0⩽Bi⩽100001\leqslant i\leqslant N;\ 0\leqslant A_i\leqslant N;\ 0\leqslant B_i\leqslant 10\, 0001iN; 0AiN; 0Bi10000
请注意在 LibreOJ 上共有 555 个子任务,其中第一个子任务为样例。