Marble Slabs

Sejun, an ancient sculptor, needs several rectangular marble slabs for a new work. The usable slab sizes are W1×H1, W2×H2, ..., Wn×Hn.

He has one large rectangular marble slab. It may be cut all the way across at any integer position, either horizontally or vertically, producing two rectangles. Separate pieces cannot be joined back together to make a larger slab. The stone also has a fixed grain direction, so pieces cannot be rotated: a piece cut as A×B cannot be used as a B×A slab. Any remaining piece that cannot be used as one of the desired sizes is discarded. Sejun wants to minimize the total discarded area.

For instance, suppose the original slab is 21×11 and the usable sizes are 10×4, 6×2, 7×5, and 15×10. Cutting as shown in the figure produces two 10×4 slabs, three 6×2 slabs, and three 7×5 slabs, with discarded area 10. Making even one 15×10 slab would increase the total loss, so the best plan does not make one.

Given the original size and the usable slab sizes, find the minimum possible total discarded area. The number of slabs produced of each usable size does not matter; only the discarded area matters.

The first line contains W and H, the width and height of the original slab. The second line contains N, the number of usable slab sizes. Each of the next N lines contains the width and height of one usable slab size.

1 ≤ W, H ≤ 600 and 0 < N ≤ 200. Every usable width and height is at least 1 and at most the corresponding dimension of the original slab.

Print one integer: the minimum discarded area possible after cutting the original slab optimally.