1016 - Container 2D

Description

There is a container having horizontal size W and vertical size H. There are N rectangle items 1, 2, ..., N in which item i has horizontal size w_i and vertical size h_i. Find the way to place these N items into the container such that:

• The sides of items are packed in parallel with the sides of the container;
• The items cannot rotated;
• No two items overlap.

 

Input

The input consists of following lines:

Line 1: contains two integer H and W (1≤ H,W≤ 30)

Line 2: contains N (1≤ N≤ 12)

Line i+2 (i=1,2,...,N): contains two integers h_i and w_i

Output

The output contains a unique number 0 (if we cannot place items) or 1 (if we can place items).

Sample Input

6 4
3
2 3
6 1
4 3

Sample Output

1

Hint

Source

• Submit
• Summary
• Discuss