Phidias#2126
The renowned sculptor of ancient Greece, Phidias, is preparing to construct another remarkable monument. To achieve this, he requires marble rectangular tiles of specific dimensions: W_1 \times H_1, W_2 \times H_2, , W_N \times H_N.
Recently, Phidias acquired a large rectangular marble slab. He intends to cut this slab to produce tiles of the specified sizes. The slab or any tile can only be divided by making a vertical or horizontal cut, resulting in two rectangular tiles. Each cut must extend from one edge to the opposite edge. This is the sole method for cutting slabs and tiles. Once cut, tiles cannot be reassembled. Due to the marble's pattern, tiles cannot be rotated; a tile of size A \times B cannot be used as a tile of B \times A, unless A = B. Phidias can cut or more tiles of each required size, and tiles of other sizes may be produced but will not be used. Phidias aims to cut the slab in such a way that the total area of unused tiles is minimized.
For instance, suppose the slab has a width of and a height of , and the specified tile sizes are: 10 \times 4, 6 \times 2, 7 \times 5, and 15 \times 10. In this scenario, the minimum possible area of unused tiles is . The illustration demonstrates one possible method of cutting the slab.
Your task is to write a program that, given the dimensions of the initial slab and the required tile sizes, computes the minimum total area of unused tiles.
The first line of the input file contains two integers. The first integer represents the width of the slab, and the second integer represents the height of the slab (1 \leq W \leq 600, 1 \leq H \leq 600). The second line contains one integer (0 < N \leq 200) — the number of required tile sizes. The following lines specify the required tile sizes. Each line contains two integers: W_i — the width and H_i — the height (1 \leq W_i \leq W, 1 \leq H_i \leq H, 1 \leq i \leq N).
The output file should contain a single integer — the minimum total area of unused tiles.
Example 1