Marble Cutting for Minimal Waste

Fidias has received a rectangular marble block and needs to obtain rectangular marble plates of sizes \(W_1 \times H_1, W_2 \times H_2, \dots, W_N \times H_N\) for his statue. He can cut the block by making a full vertical or horizontal cut (through the entire board) at an integer coordinate. The produced pieces from a cut are always rectangular and must have integer width and height. At every step, he is only allowed to cut one rectangle into two pieces. Note that the board (and any sub-board produced from a cut) cannot be rotated. In other words, if a piece of size \(A \times B\) is produced, it can only be used for a required plate that exactly matches \(A \times B\) (unless \(A = B\), in which case it is a square, and rotation has no effect).

For each of the required plate sizes, Fidias is allowed to produce zero or more pieces. At the end, any piece that does not exactly match one of the required sizes is considered waste. Your task is to determine a cutting strategy so that the total area of waste is minimized.

For instance, if the original board has width \(21\) and height \(11\), and the required plate sizes are \(10 \times 4\), \(6 \times 2\), \(7 \times 5\) and \(15 \times 10\), then the minimum total waste area achievable is \(10\). The figure below shows one cutting strategy that results in this minimal waste:

Input restrictions: All cuts must be made along the entire width or height of the current board and at an integer position. The board cannot be rotated. If the board exactly matches one of the required sizes, it is valid and produces zero waste (if used as is). Otherwise, pieces not exactly matching a required size will add to the waste.

inputFormat

The input contains several lines:

1. The first line contains two positive integers \(W\) and \(H\) representing the width and height of the original marble block.
2. The second line contains a positive integer \(N\), the number of required plate sizes.
3. Each of the following \(N\) lines contains two positive integers \(w_i\) and \(h_i\) representing a required plate size of width \(w_i\) and height \(h_i\).

You may assume that all dimensions are positive integers.

outputFormat

Output a single integer representing the minimum total waste area after cutting the original board optimally.

sample

21 11
4
10 4
6 2
7 5
15 10

10