有一天,wyb漂泊到了一个荒岛上,上面住满了食人族落。为了保全自身,他决定收买食人族部落的所有酋长,成为食人族部落的真正领导者。
收买一个酋长有两种方式:
给这名酋长 mim_{i}mi 头猪。
已经成功收买了 pip_{i}pi 名酋长。
因为wyb囊中羞涩,他希望知道怎样能用最少的猪收买所有的酋长,你能帮帮他吗?
第一行输入一个整数 nnn,表示一共有 nnn 名酋长。
接下来输入 nnn 行,第 iii 行为用空格隔开的整数 pi,mip_{i},m_{i}pi,mi
输出一行一个整数,表示所需要的最少的猪的数量
6 2 6 2 3 2 8 2 7 4 4 5 5
7
wyb需要使用3头猪收买2号酋长,4头猪收买5号酋长。此时收买的酋长数为2,则1、3、4号酋长也会听从wyb。则此时收买的酋长数为5,6号酋长也会听从wyb。至此,所有的酋长都被收买了,最终答案为7。
3 1 5 2 10 2 8
8
wyb需要使用8头猪收买3号酋长。此时收买的酋长数为1,则1号酋长也会听从wyb。则此时收买的酋长数为2,2号酋长也会听从wyb。至此,所有的酋长都被收买了,最终答案为8。
1≤n≤2×1051\leq n \leq 2×10^{5}1≤n≤2×105
1≤mi≤109,0≤pi≤n1\leq m_{i} \leq 10^{9}, 0 \leq p_{i} \leq n1≤mi≤109,0≤pi≤n
注意 pip_{i}pi 可能为0,表示这名酋长已经被wyb的人格魅力收买了,不需要送出猪了。