103453: [Atcoder]ABC345 D - Tiling

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.

问题描述

有一个由$H$行和$W$列组成的网格，每个单元格的边长为1，我们有$N$个瓷砖。

第$i$个瓷砖（$1\leq i\leq N$）是一个长宽分别为$A_i\times B_i$的矩形。

确定是否可以将瓷砖放在网格上，使以下所有条件都得到满足：

• 每个单元格恰好被一个瓷砖覆盖。
• 可以有未使用的瓷砖。
• 放置瓷砖时可以旋转或翻转。但是，每个瓷砖必须与单元格的边缘对齐，而不能超出网格。

约束

• $1\leq N\leq 7$
• $1 \leq H,W \leq 10$
• $1\leq A_i,B_i\leq 10$
• 所有输入值都是整数。

输入

输入从标准输入按以下格式给出：

$N$ $H$ $W$
$A_1$ $B_1$
$A_2$ $B_2$
$\ldots$
$A_N$ $B_N$

输出

如果可以将瓷砖放在网格上，使问题描述中的所有条件都得到满足，打印Yes；否则，打印No。

样例输入1

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

样例输出1

Yes

将第2个、第4个和第5个瓷砖按照如下方式放置，可以使网格的每个单元格恰好被一个瓷砖覆盖。

因此，打印Yes。

样例输入2

1 1 2
2 3

样例输出2

No

不可能不超出网格放置瓷砖。

因此，打印No。

样例输入3

1 2 2
1 1

样例输出3

No

不可能用瓷砖覆盖所有单元格。

因此，打印No。

样例输入4

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

样例输出4

No

注意每个单元格必须恰好被一个瓷砖覆盖。