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

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

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

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

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