Jaher's suitcase P52363

Statement

thehtml

[r]

Jaher is a brilliant algorithmist, but he is also a bit absent minded. For example, he has some difficulties making things fit into his suitcase. Can you help him?

For simplicity, let us assume a two-dimensional suitcase a × b, where n ‍rectangular objects must fit. Objects can be placed at any position within the suitcase, without overlap, but they can not be rotated. In how many ways can we put the objects?

Input

Input consists of several cases. Each case begins with a, b and n. Follow n pairs of strictly positive natural numbers, which indicate the sizes of the objects. The area of the objects exactly covers the suitcase, and there is always at least one possible solution. (The first case in the sample input corresponds to the picture.)

Output

[r]

For every suitcase, print a line with its number and how many possible solutions exist.

Public test cases

Input

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

2 3 2
2 2   2 1

1 1 1
1 1

1 5 3
1 1   1 2   1 2

6 8 10
3 4   1 6   2 3   1 1   2 2
1 4   2 1   2 5   1 2   1 1

Output

#1: 32
#2: 2
#3: 1
#4: 6
#5: 4384

Information

Author: Salvador Roura
Language: English
Translator: Salvador Roura
Original language: Catalan
Other languages: Catalan
Official solutions: C++
User solutions: C++