#1201. wyb的食人族部落

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

题目描述

有一天,wyb漂泊到了一个荒岛上,上面住满了食人族落。为了保全自身,他决定收买食人族部落的所有酋长,成为食人族部落的真正领导者。

收买一个酋长有两种方式:

  1. 给这名酋长 mim_{i} 头猪。

  2. 已经成功收买了 pip_{i} 名酋长。

因为wyb囊中羞涩,他希望知道怎样能用最少的猪收买所有的酋长,你能帮帮他吗?

输入格式

第一行输入一个整数 nn,表示一共有 nn 名酋长。

接下来输入 nn 行,第 ii 行为用空格隔开的整数 pi,mip_{i},m_{i}

输出格式

输出一行一个整数,表示所需要的最少的猪的数量

样例

样例输入1

6
2 6
2 3
2 8
2 7
4 4
5 5

样例输出1

7

样例解释1

wyb需要使用3头猪收买2号酋长,4头猪收买5号酋长。此时收买的酋长数为2,则1、3、4号酋长也会听从wyb。则此时收买的酋长数为5,6号酋长也会听从wyb。至此,所有的酋长都被收买了,最终答案为7。

样例输入2

3
1 5
2 10
2 8

样例输出2

8

样例解释2

wyb需要使用8头猪收买3号酋长。此时收买的酋长数为1,则1号酋长也会听从wyb。则此时收买的酋长数为2,2号酋长也会听从wyb。至此,所有的酋长都被收买了,最终答案为8。

数据范围与提示

1n2×1051\leq n \leq 2×10^{5}

1mi109,0pin1\leq m_{i} \leq 10^{9}, 0 \leq p_{i} \leq n

注意 pip_{i} 可能为0,表示这名酋长已经被wyb的人格魅力收买了,不需要送出猪了。