P5924 [IOI 2004] Phidias Phidias the Sculptor

The famous Greek master sculptor Phidias is preparing for his next magnificent statue.

For this statue, he needs rectangular marble slabs of sizes $W_1\times H_1, W_2\times H_2, \ldots, W_N \times H_N$. Recently, Phidias obtained a rectangular marble block. He wants to cut it into the required sizes. A slab, or any piece cut from it, can be cut all the way through by a vertical (or horizontal) straight cut into two rectangular slabs. The two resulting slabs must both have integer widths and heights. The slab can only be cut in this way, and slabs cannot be glued together into a larger slab. Because the slab has a pattern, it cannot be rotated. If Phidias cuts out a slab of size $A\times B$, then it cannot be used as a $B\times A$ slab unless $A = B$. For each required slab size, Phidias may cut out zero or more slabs. After all cuts are finished, any produced slab whose size is not among the required sizes becomes waste. Phidias wants to know how to cut the original slab so that the total waste area is minimized. For example, in the figure below, the original slab has width $21$ and height $11$, and the required sizes are $10\times4$, $6\times2$, $7\times5$, and $15\times10$. Then the minimum total waste area is $10$. The figure also shows a cutting plan that achieves the minimum waste area of $10$:  Your task is to write a program that, given the size of the original slab and the required slab sizes, computes the minimum total waste area.

The first line contains two integers. The first integer $W$ is the width of the original slab, and the second integer $H$ is the height of the original slab. The second line contains an integer $N$, the number of required slab types. The next $N$ lines give the sizes of the required slabs. Each line contains two integers: the first is the required slab width $W_i$, and the second is the required slab height $H_i$.

Output one line containing exactly one integer, the minimum total waste area.

Constraints: for $100\%$ of the testdata, $1\le W, H\le 600$, $0\le N\le 200$, $1 \le W_i \le W$, $1 \le H_i \le H$. Translated by ChatGPT 5