该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“赛后递交”以递交本题。

题目描述

小 Z 有一个 $n \times m$ 大小的矩形猫窝（单位：厘米）。现在有 $k$ 只猫猫，第 $i$ 只猫猫占据的空间是一个 $a_i \times b_i$ 的矩形（单位：厘米）。

小 Z 需要将猫猫放入猫窝中，满足以下条件：

• 每只猫猫占据的矩形区域必须完全在猫窝内部；
• 不同猫猫占据的区域不能重叠；
• 猫猫可以旋转（即 $a_i \times b_i$ 可以变为 $b_i \times a_i$）；
• 猫猫不能被压缩或拉扯，必须保持矩形形状；

你的任务是计算猫窝中最多能容纳多少只猫猫。

输入格式

第一行三个整数 $k, n, m$，分别表示猫猫数量、猫窝的长和宽。

接下来 $k$ 行，每行两个整数 $a_i, b_i$，表示第 $i$ 只猫猫的长和宽。

输出格式

输出一个整数，表示最多能容纳的猫猫数量。

输入输出样例

5 5 5
1 4
1 1
2 2
5 5
3 4

4

样例 #1说明

• 可以放下猫猫 $1（1×4）$、猫猫 $2（1×1）$、猫猫 $3（2×2）$、猫猫 $5（3×4$ 旋转为$4×3）$，猫猫 $4（5×5）$太大放不下。

3 10 8
6 4
5 3
3 2

3

数据范围

• 子任务 1（30分）： $k \leq 5, n,m \leq 8$
• 子任务 2（30分）： $k \leq 8, n,m \leq 10$
• 子任务 3（40分）： $k \leq 10, n,m \leq 12$
• 子任务 4（20分）： $k \leq 10, n,m \leq 20$
• 对于所有数据：$1 \leq a_i, b_i \leq \min(n,m)$，且所有猫猫的尺寸均为整数