Description

小刚在玩JSOI提供的一个称之为“建筑抢修”的电脑游戏：经过了一场激烈的战斗，T部落消灭了所有z部落的入侵者。但是T部落的基地里已经有N个建筑设施受到了严重的损伤，如果不尽快修复的话，这些建筑设施将会完全毁坏。现在的情况是：T部落基地里只有一个修理工人，虽然他能瞬间到达任何一个建筑，但是修复每个建筑都需要一定的时间。同时，修理工人修理完一个建筑才能修理下一个建筑，不能同时修理多个建筑。如果某个建筑在一段时间之内没有完全修理完毕，这个建筑就报废了。你的任务是帮小刚合理的制订一个修理顺序，以抢修尽可能多的建筑。

Input

第一行是一个整数N，接下来N行每行两个整数T1,T2描述一个建筑：修理这个建筑需要T1秒，如果在T2秒之内还没有修理完成，这个建筑就报废了。

Output

输出一个整数S，表示最多可以抢修S个建筑。 数据范围： N<150000，T1

Sample Input

4

100 200

200 1300

1000 1250

2000 3200

Sample Output

3

 

先对t2进行排序，然后一个个加入

如果now+t1<=t2，就直接加入

如果now+t1>t2，那么就用它和已经加入的时间最大的比较，如果t1比它小就替换它

用大根堆维护最大时间

1 const  2     maxn=150010;  3    4 type  5     node=record  6       t1,t2:longint;  7     end;  8    9 var 10     a:array[0..maxn]of node; 11     n:longint; 12   13 procedure swap(var x,y:node); 14 var 15     t:node; 16 begin 17     t:=x;x:=y;y:=t; 18 end; 19   20 procedure sort(l,r:longint); 21 var 22     i,j,y:longint; 23 begin 24     i:=l;j:=r; 25     y:=a[(l+r)>>1].t2; 26     repeat 27       while a[i].t2
      
       y do 30         dec(j); 31       if i<=j then 32       begin 33         swap(a[i],a[j]); 34         inc(i); 35         dec(j); 36       end; 37     until i>j; 38     if i
       
        l then sort(l,j); 40 end; 41   42 procedure init; 43 var 44     i:longint; 45 begin 46     read(n); 47     for i:=1 to n do 48       with a[i] do 49         read(t1,t2); 50     sort(1,n); 51 end; 52   53 var 54     q:array[0..maxn]of node; 55     now,tot:longint; 56   57 procedure down(x:longint); 58 var 59     i:longint; 60 begin 61     i:=x<<1; 62     while i<=tot do 63       begin 64         if (i
        
         q[i].t1) then inc(i); 65         if q[x].t1
         
          1 do 80       begin 81         i:=x>>1; 82         if q[x].t1>q[i].t1 then 83           begin 84             swap(q[i],q[x]); 85             x:=i; 86             i:=x>>1; 87           end 88         else break; 89       end; 90 end; 91   92 procedure work; 93 var 94     i:longint; 95 begin 96     for i:=1 to n do 97       if now+a[i].t1<=a[i].t2 then 98         begin 99           inc(tot);100           q[tot]:=a[i];101           up(tot);102           inc(now,a[i].t1);103         end104       else105         if a[i].t1