Problem10079--ABC345 —— D - Tiling

10079: ABC345 —— D - Tiling

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MiB

Description

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.

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`.

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.

Sample 1 Input

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

Sample 1 Output

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 2 Input

1 1 2
2 3

Sample 2 Output

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

Sample 3 Input

1 2 2
1 1

Sample 3 Output

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

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

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

Source/Category