The First Acceptance

Time Limit : 1 sec, Memory Limit : 262144 KB

問題 E : ファーストアクセプタンス

プログラミングコンテストでは,各問題に関して, その問題を最初に正解した人の名前や正解時間が, ファーストアクセプタンス(最初の正解)として解説等でしばしば言及される.

久しぶりにプログラミングコンテストに参加するとはいえ,予選で落ちるとは到底思えない. ならば,最初のうちは,多少高いスコアを取ることを目指すよりも, ファーストアクセプタンスを多く獲得し,存在をアピールしたほうが良いのではないか.

自分の実力を持ってすれば,各問題を見た瞬間に, その問題を自分が何分で解くことができるかと, その問題が開始後何分で自分以外の参加者によって最初に解かれるかがわかる.

これらの情報を用いて, どの程度ファーストアクセプタンスを獲得できるかを計算するプログラムを作っておこう.

問題

N 問の問題から成るプログラミングコンテストを考える. 問題 i を自分が解くには Ai 秒の時間がかかり, また,問題 i は開始後 Bi 秒で自分以外の参加者によって最初に解かれるとする.

自分が問題を解く順番は自由に決められるが, 1 つの問題を解き始めたら,解き終えるまでその問題をやるものとする. 問題を解き終え次の問題に取りかかる際などの, 問題を解いている時間以外の時間は十分小さいと考え,無視して考えることにする. また,全ての問題は終了までに 1 人以上の自分以外の参加者によって解かれるものと考える.

自分以外の参加者によって最初に解かれるよりも早く, あるいは同時に問題 i を自分が解きおえた時, 問題 i のファーストアクセプタンスを獲得できる. すなわち,問題 i を自分が開始後 ti 秒に解き終えたとしたとき, ti ≤ Bi であれば,問題 i のファーストアクセプタンスを獲得できる.

最大で何個の問題に関してファーストアクセプタンスが獲得できるかを計算するプログラムを作成せよ.

入力

入力の最初の行は 1 つの整数 N を含む.

続く N 行には,各問題に関する情報が与えられる. これらの行のうちの i 行目には 2 個の数字 AiBi が書かれている.

出力

最大で獲得することのできるファーストアクセプタンスの数を出力せよ.

制約

  • 1 ≤ N ≤ 1000
  • 1 ≤ Ai ≤ 106 (1 ≤ i ≤ N)
  • 1 ≤ Bi ≤ 106 (1 ≤ i ≤ N)

部分点

この問題の判定には,20 点分のテストケースのグループが設定されている. このグループに含まれるテストケースの入力は以下を満たす.

  • 1 ≤ N ≤ 16

入出力例

入出力例 1

入力例 1:

3
3 5
5 9
10 20

入力例 1 に対する出力例:

3

入出力例 2

入力例 2:

3
3 2
5 15
10 12

入力例 2 に対する出力例:

2

Source: University of Tokyo Programming Contest 2011 , Tokyo, Japan, 2011-05-14
Problem Setter:  Takuya Akiba
http://www.utpc.jp/2011/