Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 2479
Cover the Rectangular Ground

Time Limit: 2 Seconds      Memory Limit: 65536 KB

A company has bought several rectangular blocks of different sizes, and wants to cover a big rectangular blank ground with some of them. But there is a restriction of covering that the blocks to cover the blank ground should not be overlapped and cannot go beyond the edges of the blank ground. At first, the company wants to know whether there exists a way that some of the blocks can cover the blank ground with the restriction mentioned above. So can you help this company?

To simplify the situation, we assume that there are at most seven different sizes of blocks (note: the size of the block with width 5 and length 4 is considered to be the same as the block with width 4 and length 5, because they are rectangles and can be rotated).

Input

There are several test cases. In the first line, there is a positive integer N, which is the number of the test cases. Then following N test cases, in each test case, the first line contains two positive integers, W and L, which represent the width and length of the rectangular blank ground respectively (W <=20, L <=20); the second line contains a positive integer M (M <=10), which represents the number of blocks that this company has bought. Then following M lines, each line contains two positive integers, which represent the width and length of a block respectively.

Output

For each test case, you should output one line. If there exists a way that using some of these blocks can cover the blank ground with the restriction mentioned above, then output "YES"; otherwise output "NO".

Sample Input

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

Sample Output

YES
NO

Author: XU, Luchuan
Source: Zhejiang Provincial Programming Contest 2005
Submit    Status