Phidias
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×H_1, W_2×H_2, ..., W_N×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×B cannot be used as a tile of B×A, unless A = B. Phidias can cut 0 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 21 and a height of 11, and the specified tile sizes are: 10×4, 6×2, 7×5, and 15×10. In this scenario, the minimum possible area of unused tiles is 10. 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.
Input
The first line of the input file contains two integers. The first integer W represents the width of the slab, and the second integer H represents the height of the slab (1 ≤ W ≤ 600, 1 ≤ H ≤ 600). The second line contains one integer N (0 < N ≤ 200) – the number of required tile sizes. The following N lines specify the required tile sizes. Each line contains two integers: W_i – the width and H_i – the height (1 ≤ W_i ≤ W, 1 ≤ H_i ≤ H, 1 ≤ i ≤ N).
Output
The output file should contain a single integer – the minimum total area of unused tiles.