0283 - 微生物実験 (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 は，この摂取量が b_i より大きいと死んでしまう．
　JOI 社からの委託により，あなたは出来るだけ多くの微生物をシャーレに生きたまま閉じ込めなければならない．ただし，微生物の死骸はシャーレ内の環境に悪影響を及ぼすため，シャーレ内のどの微生物も foo の摂取で死んではならない．
　なお，JOI 社が「ただ奇妙な発明」をすることでどうやって利益を得ているかは，今もって謎であり，JOI 社内でも社長以外の誰も知らない．

課題

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

制限

1 ≤ N ≤ 300 000 = 3 × 10⁵    調査対象の微生物の数
1 ≤ a_i ≤ 100 000 = 10⁵    微生物 i の foo 放出量(ミリグラム)
1 ≤ b_i ≤ 100 000 = 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 ≤ 1 000 を満たす．

入出力例

入力例 1

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

出力例 1

3

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