Score: $450$ points

问题陈述

有一个由 $H$ 行和 $W$ 列组成的网格，每个单元格的边长为 $1$，我们有 $N$ 块瓷砖。 第 $i$ 块瓷砖（$1\leq i\leq N$）是一个大小为 $A_i\times B_i$ 的矩形。 确定是否可能将瓷砖放置在网格上，以满足以下所有条件：

• 每个单元格恰好被一块瓷砖覆盖。
• 有未使用的瓷砖是可以接受的。
• 放置瓷砖时可以旋转或翻转。然而，每个瓷砖必须与单元格的边缘对齐，不得延伸到网格外部。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

There is a grid of $H$ rows and $W$ columns, each cell having a side length of $1$, and we have $N$ tiles.
The $i$-th tile ($1\leq i\leq N$) is a rectangle of size $A_i\times B_i$.
Determine whether it is possible to place the tiles on the grid so that all of the following conditions are satisfied:

• Every cell is covered by exactly one tile.
• It is fine to have unused tiles.
• The tiles may be rotated or flipped when placed. However, each tile must be aligned with the edges of the cells without extending outside the grid.

Constraints

• $1\leq N\leq 7$
• $1 \leq H,W \leq 10$
• $1\leq A_i,B_i\leq 10$
• All input values are integers.

Input

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

$N$ $H$ $W$

$A_1$ $B_1$

$A_2$ $B_2$

$\ldots$

$A_N$ $B_N$

Output

If it is possible to place the tiles on the grid so that all of the conditions in the problem statement are satisfied, print Yes; otherwise, print No.

Sample Input 1

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

Sample Output 1

Yes

Placing the $2$-nd, $4$-th, and $5$-th tiles as shown below covers every cell of the grid by exactly one tile.

Hence, print Yes.

Sample Input 2

1 1 2
2 3

Sample Output 2

No

It is impossible to place the tile without letting it extend outside the grid.
Hence, print No.

Sample Input 3

1 2 2
1 1

Sample Output 3

No

It is impossible to cover all cells with the tile.
Hence, print No.

Sample Input 4

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

Sample Output 4

No

Note that each cell must be covered by exactly one tile.

update @ 2024/5/16 17:16:52