B - AtCoder Alloy Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

AtCoder 合金と呼ばれる特殊な金属でできた，長方形の板状の素材が N 枚あります． i 番目の素材の縦の長さは A_i，横の長さは B_i です．

高橋君は，AtCoder 合金でできた，縦の長さがちょうど H，横の長さがちょうど W の長方形の板が欲しいです． そのため，N 枚の素材のうち 1 枚を選び，それを必要に応じて切断して，求める長方形の板を得ようとしています． 素材を切断する際には，長方形の辺に平行な線でしか切断することができません． また，素材には向きが定まっているので，回転させることはできません． そのため，例えば縦 5，横 3 の素材を，縦 3，横 5 の板として使うことはできません．

適切に切断することで，長さが縦 H，横 W の板が得られるような素材は N 枚中何枚あるでしょうか？

制約

  • 1 \leq N \leq 1000
  • 1 \leq H \leq 10^9
  • 1 \leq W \leq 10^9
  • 1 \leq A_i \leq 10^9
  • 1 \leq B_i \leq 10^9
  • 入力はすべて整数

入力

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

N H W
A_1 B_1
A_2 B_2
:
A_N B_N

出力

答えを出力せよ．

入力例 1

3 5 2
10 3
5 2
2 5

出力例 1

2

高橋君は，縦 5，横 2 の大きさの板が欲しいです．

  • 1 番目の素材は，縦 10，横 3 の大きさで，適切に切断すると縦 5，横 2 の大きさの板が得られます．
  • 2 番目の素材は，縦 5，横 2 の大きさで，切断せずに縦 5，横 2 の大きさの板が得られます．
  • 3 番目の素材は，縦 2，横 5 の大きさで，どのように切断しても 縦 5，横 2 の大きさの板は得られません．素材を回転させて縦 5，横 2 の大きさの板として使うことはできないことに注意してください．

入力例 2

10 587586158 185430194
894597290 708587790
680395892 306946994
590262034 785368612
922328576 106880540
847058850 326169610
936315062 193149191
702035777 223363392
11672949 146832978
779291680 334178158
615808191 701464268

出力例 2

8

Score : 200 points

Problem Statement

There are N rectangular plate materials made of special metal called AtCoder Alloy. The dimensions of the i-th material are A_i \times B_i (A_i vertically and B_i horizontally).

Takahashi wants a rectangular plate made of AtCoder Alloy whose dimensions are exactly H \times W. He is trying to obtain such a plate by choosing one of the N materials and cutting it if necessary. When cutting a material, the cuts must be parallel to one of the sides of the material. Also, the materials have fixed directions and cannot be rotated. For example, a 5 \times 3 material cannot be used as a 3 \times 5 plate.

Out of the N materials, how many can produce an H \times W plate if properly cut?

Constraints

  • 1 \leq N \leq 1000
  • 1 \leq H \leq 10^9
  • 1 \leq W \leq 10^9
  • 1 \leq A_i \leq 10^9
  • 1 \leq B_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N H W
A_1 B_1
A_2 B_2
:
A_N B_N

Output

Print the answer.

Sample Input 1

3 5 2
10 3
5 2
2 5

Sample Output 1

2

Takahashi wants a 5 \times 2 plate.

  • The dimensions of the first material are 10 \times 3. We can obtain a 5 \times 2 plate by properly cutting it.
  • The dimensions of the second material are 5 \times 2. We can obtain a 5 \times 2 plate without cutting it.
  • The dimensions of the third material are 2 \times 5. We cannot obtain a 5 \times 2 plate, whatever cuts are made. Note that the material cannot be rotated and used as a 5 \times 2 plate.

Sample Input 2

10 587586158 185430194
894597290 708587790
680395892 306946994
590262034 785368612
922328576 106880540
847058850 326169610
936315062 193149191
702035777 223363392
11672949 146832978
779291680 334178158
615808191 701464268

Sample Output 2

8