Description

　　小剛在玩JSOI提供的一個稱之為“建筑搶修”的電腦游戲：經(jīng)過了一場激烈的戰(zhàn)斗，T部落消滅了所有z部落的入侵者。但是T部落的基地里已經(jīng)有N個建筑設(shè)施受到了嚴重的損傷，如果不盡快修復(fù)的話，這些建筑設(shè)施將會完全毀壞。現(xiàn)在的情況是：T部落基地里只有一個修理工人，雖然他能瞬間到達任何一個建筑，但是修復(fù)每個建筑都需要一定的時間。同時，修理工人修理完一個建筑才能修理下一個建筑，不能同時修理多個建筑。如果某個建筑在一段時間之內(nèi)沒有完全修理完畢，這個建筑就報廢了。你的任務(wù)是幫小剛合理的制訂一個修理順序，以搶修盡可能多的建筑。

Input

　　第一行是一個整數(shù)N接下來N行每行兩個整數(shù)T1,T2描述一個建筑：修理這個建筑需要T1秒，如果在T2秒之內(nèi)還沒有修理完成，這個建筑就報廢了。

Output

　　輸出一個整數(shù)S，表示最多可以搶修S個建筑.N < 150,000; T1 < T2 < maxlongint

Sample Input

4 100 200 200 1300 1000 1250 2000 3200

Sample Output

3

題解

先按t2排序， 在把已經(jīng)修好的建筑加入一個堆里。 對于一個接下來的建筑，如果從當前開始修好，就修好它，并把它加入堆中。 如果當前不能修好，就把這棟建筑的修理時間和堆中花費時間最長的進行比較，看能否放棄堆中的那個建筑而來修當前建筑，若能，則再進行修改。

代碼