← 返回题目列表

AtCoder · caddi2018b_b

B. AtCoder 合金

中文机器翻译题面 查看原题

分数: 200 点

问题陈述

有 N 由称为 AtCoder 合金的特殊金属制成的矩形板材料。 的尺寸 i第材料是 A_i \times B_i (A_i 垂直和 B_i 水平)。

Takahashi 想要一块由 AtCoder 合金制成的矩形板,其尺寸恰好为 H \times W。 他试图通过选择其中一个来获得这样的盘子 N 材料并根据需要进行切割。 切割材料时,切口必须平行于材料的一侧。 而且,材料有固定的方向,不能旋转。 例如,一个 5 \times 3 材料不能用作 3 \times 5 板。

出 N 材料,可以生产多少个 H \times W 板材是否正确切割?

约束

  • 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 \times 2 板。

  • 第一种材料的尺寸为 10 \times 3。我们可以得到一个 5 \times 2 板通过正确切割它。
  • 第二种材料的尺寸为 5 \times 2。我们可以得到一个 5 \times 2 板材无需切割。
  • 第三种材料的尺寸为 2 \times 5。我们无法获得 5 \times 2 板,无论进行何种切割。请注意,该材料不能旋转并用作 5 \times 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