Carpets

Time limit1sMemory limit256 MB

Summary

Decide whether the given carpets, each usable rotated, cover a W by H room exactly with no overlap.

Level: Medium6 of 10
Topics: Backtracking, Recursion
Solved: No attempts yet

Problem

Professor Toving Liles of the computer science department likes the floor tiles in his office so much that he wants to protect them from careless students. He plans to buy cheap small rectangular carpets at the supermarket and cover the floor so that all four rules hold:

The entire floor is covered.
No two carpets overlap.
A carpet may be turned by 90 degrees, so a $w \times h$ carpet can also be laid as an $h \times w$ carpet.
No carpet is cut into pieces.

Every carpet is laid with its sides parallel to the walls, and the professor does not have to buy the whole stock. Decide whether he can carry out his plan.

Input

The first line contains two integers $W$ and $H$ , the width and the height of the room ( $1 \le W, H \le 100$ ).

The second line contains an integer $c$ , the number of carpet colors the supermarket has in stock ( $1 \le c \le 7$ ).

Each of the following $c$ lines contains three integers $a_i$ , $w_i$ and $h_i$ , meaning that the supermarket has $a_i$ carpets of size $w_i \times h_i$ in color $i$ ( $1 \le a_i \le 7$ ; $1 \le w_i \le 100$ ; $1 \le h_i \le 100$ ).

The supermarket has at most 7 carpets in total, that is $\sum_i a_i \le 7$ .

Output

Print yes if the room can be covered under the rules above, and no otherwise.

Examples2

Example 1
Input
```
2 4
2
3 1 3
2 2 1
```
Expected output
```
yes
```
Example 2
Input
```
100 100
3
4 42 42
1 100 16
1 32 42
```
Expected output
```
no
```