微生物実験(Bug Party)

あなたはJust Odd Inventions 社を知っているだろうか? この会社の業務は「ただ奇妙な発明(just odd inventions)」をすることである．ここでは略してJOI 社と呼ぶ．

JOI 社では多くの微生物を1 つのシャーレに生きたまま閉じ込める研究をしている．調査対象の微生物はN 匹存在し，1, 2, ... , N という番号がついている．各微生物はシャーレに閉じ込められると，foo (fatally odd object) と呼ばれる有害物質を一瞬のうちにシャーレ内に放出する．各微生物が放出するfoo の量は知られている．シャーレに閉じ込められた全微生物が放出したfoo はシャーレ内の各微生物が均等に摂取する．各微生物のfoo 許容量は知られており，この量を超えてfoo を摂取すると微生物は死んでしまう．

微生物i のfoo 放出量はa_i ミリグラム，foo 許容量はb_i ミリグラムである．すなわち，シャーレに微生物i₁, i₂, ... , i_k を閉じ込めたとき，シャーレ内の各微生物はそれぞれ(a_i1 + a_i2 + ... + a_ik)/k ミリグラムのfoo を摂取し，シャーレ内の微生物i は，この摂取量がbi より大きいと死んでしまう．

JOI 社からの委託により，あなたは出来るだけ多くの微生物をシャーレに生きたまま閉じ込めなければならない．ただし，微生物の死骸はシャーレ内の環境に悪影響を及ぼすため，シャーレ内のどの微生物もfoo の摂取で死んではならない．

なお，JOI 社が「ただ奇妙な発明」をすることでどうやって利益を得ているかは，今もって謎であり，JOI社内でも社長以外の誰も知らない．

課題

調査対象の微生物数と，各微生物のfoo 放出量とfoo 許容量が与えられたとき，1 つのシャーレに閉じ込めることができる微生物数の最大値を求めるプログラムを作成せよ．

制限

1 ≤ N ≤ 300000 = 3 × 10⁵    調査対象の微生物の数
1 ≤ a_i ≤ 100000 = 10⁵    微生物i のfoo 放出量(ミリグラム)
1 ≤ b_i ≤ 100000 = 10⁵    微生物i のfoo 許容量(ミリグラム)

入力

標準入力から以下の入力を読み込め．

• 1 行目には整数N が書かれており，調査対象の微生物がN 匹存在することを表す．
• 続くN 行には各微生物の情報が書かれている．i + 1 行目(1 ≤ i ≤ N) には，正整数 a_i, b_i が空白を区切りとして書かれており，微生物i のfoo 放出量がa_i ミリグラムでfoo 許容量がb_i ミリグラムであることを表す.

出力

標準出力に，1 つのシャーレに閉じ込めることができる微生物数の最大値を1 行で出力せよ．

注意

この問題では，扱う整数の範囲が32 ビットに収まらない可能性があることに注意せよ．

採点基準

採点用データのうち，配点の30% については，N ≤ 1000 を満たす．

入出力の例

入力例

6
12 8
5 9
2 4
10 12
6 7
13 9

出力例

3

この例では，微生物2, 4, 5 をシャーレに入れれば，放出されるfoo の合計量は5 + 10 + 6 = 21 ミリグラムとなり，それぞれの微生物が摂取するfoo の量は21/3 = 7 ミリグラムとなる．微生物2, 4, 5 のfoo 許容量はそれぞれ9, 12, 7 ミリグラムなので，シャーレ内のどの微生物も死なない．また，4 匹以上の微生物をどの微生物も死なないようにシャーレに入れることはできない．

---