### IOI '04 - Athens, Greece

## Phidias

Famous ancient Greek sculptor Phidias is making preparations to build
another marvelous monument. For this purpose he needs rectangular marble plates
of sizes *W*_{1} × *H*_{1}, *W*_{2}
× *H*_{2}, …, *W*_{N} ×
*H*_{N}.

Recently, Phidias has received a large rectangular marble slab. He wants to
cut the slab to obtain plates of the desired sizes. Any piece of marble (the
slab or the plates cut from it) can be cut either horizontally or vertically
into two rectangular plates with integral widths and heights, cutting
completely through that piece. This is the only way to cut pieces and pieces
cannot be joined together. Since the marble has a pattern on it, the plates
cannot be rotated: if Phidias cuts a plate of size *A* × *B*
then it cannot be used as a plate of size *B* × *A* unless
*A* = *B*. He can make zero or more plates of each desired size. A
marble plate is wasted if it is not of any of the desired sizes after all cuts
are completed. Phidias wonders how to cut the initial slab so that as little of
it as possible will be wasted.

As an example, assume that in the figure below the width of the original slab is 21 and the height of the original slab is 11, and the desired plate sizes are 10 × 4, 6 × 2, 7 × 5, and 15 × 10. The minimum possible area wasted is 10, and the figure shows one sequence of cuts with total waste area of size 10.

Your task is to write a program that, given the size of the original slab and the desired plate sizes, calculates the minimum total area of the original slab that must be wasted.

### Input

The first line of input contains two integers: first*W*(1 ≤

*W*≤ 600), the width of the original slab, and then

*H*(1 ≤

*H*≤ 600), the height of the original slab. The second line contains one integer

*N*(0 <

*N*≤ 200): the number of desired plate sizes. The following

*N*lines contain the desired plate sizes. Each of these lines contains two integers: first the width

*W*

_{i}(1 ≤

*W*

_{i}≤

*W*) and then the height

*H*

_{i}(1 ≤

*H*

_{i}≤

*H*) of that desired plate size.

### Output

The output should contain one line with a single integer: the minimum total area of the original slab that must be wasted.### Sample Input

21 11 4 10 4 6 2 7 5 15 10

### Sample Output

10

Note: in 50% of the inputs, *W* ≤ 20, *H* ≤ 20, and *N* ≤ 5.

All Submissions

Best Solutions

**Point Value:** 10 (partial)

**Time Limit:** 2.00s

**Memory Limit:** 16M

**Added:** Dec 19, 2009

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...