E - Battles in a Row Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

高橋君が N 体のモンスターと順に戦うゲームで遊ぼうとしています。最初、高橋君の体力は H 、魔力は M です。

i 番目に戦うモンスターに対して、高橋君は以下のどちらかの行動を選べます。

  • 魔法を使わずに戦う。体力が A_i 以上のときのみ選ぶことができ、体力が A_i 減少しモンスターを倒す。
  • 魔法を使って戦う。魔力が B_i 以上のときのみ選ぶことができ、魔力が B_i 減少しモンスターを倒す。

N 体全てのモンスターを倒すか、高橋君が行動できなくなるとゲーム終了です。ゲーム終了までに最大で何体のモンスターを倒せますか。

制約

  • 1 \leq N \leq 3000
  • 1 \leq H,M \leq 3000
  • 1 \leq A_i,B_i \leq 3000
  • 入力は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

N H M
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

答えを出力せよ。

入力例 1

4 10 14
5 8
5 6
7 9
99 99

出力例 1

3

次のように行動することで、ゲーム終了までに 3 体のモンスターを倒すことができます。

  • 最初、高橋君の体力は 10、魔力は 14 です。
  • 1 体目のモンスターと魔法を使わずに戦う。体力が 5 減少し、体力が 5、魔力が 14 となる。
  • 2 体目のモンスターと魔法を使わずに戦う。体力が 5 減少し、体力が 0、魔力が 14 となる。
  • 3 体目のモンスターと魔法を使って戦う。魔力が 9 減少し、体力が 0、魔力が 5 となる。
  • 4 体目のモンスターとの戦いではどちらの行動も選べないためゲーム終了となる。

入力例 2

3 3000 3000
3 3
3 3
3 3

出力例 2

3

全てのモンスターを倒せることもあります。

入力例 3

10 8 8
2 2
2 3
2 2
1 2
2 3
1 2
3 3
3 2
3 1
3 2

出力例 3

9

Score : 450 points

Problem Statement

Takahashi is about to play a game where he fights N monsters in order. Initially, Takahashi's health is H and his magic power is M.

For the i-th monster he fights, he can choose one of the following actions:

  • Fight without using magic. This can only be chosen when his health is at least A_i, and his health decreases by A_i and the monster is defeated.
  • Fight using magic. This can only be chosen when his magic power is at least B_i, and his magic power decreases by B_i and the monster is defeated.

The game ends when all N monsters are defeated or when he cannot take any action. What is the maximum number of monsters he can defeat before the game ends?

Constraints

  • 1 \leq N \leq 3000
  • 1 \leq H,M \leq 3000
  • 1 \leq A_i,B_i \leq 3000
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N H M
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Output the answer.

Sample Input 1

4 10 14
5 8
5 6
7 9
99 99

Sample Output 1

3

By taking the following actions, Takahashi can defeat 3 monsters before the game ends.

  • Initially, his health is 10 and his magic power is 14.
  • Fight the 1st monster without using magic. His health decreases by 5, becoming health 5 and magic power 14.
  • Fight the 2nd monster without using magic. His health decreases by 5, becoming health 0 and magic power 14.
  • Fight the 3rd monster using magic. His magic power decreases by 9, becoming health 0 and magic power 5.
  • For the 4th monster, he cannot choose either action, so the game ends.

Sample Input 2

3 3000 3000
3 3
3 3
3 3

Sample Output 2

3

He may be able to defeat all monsters.

Sample Input 3

10 8 8
2 2
2 3
2 2
1 2
2 3
1 2
3 3
3 2
3 1
3 2

Sample Output 3

9