SP365 PHIDIAS - Phidias

**问题描述** 著名的古希腊雕刻家 Phidias 正在为他的下一个传世之作做准备。因此他需要一些尺寸为 $W_1\times H_1,W_2\times H_2,\cdots, W_N\times H_N$ 的矩形大理石板。 最近，Phidias 得到了一块巨大的矩形大理石板材。他想将板材切开以获得所需尺寸的大理石板。任何一块大理石（板材或者从它上面切下来的石板） 都可以被从纵向或横向完全切断成两块具有整数宽度和高度的矩形石板。这是切割大理石板的唯一方法并且切开的大理石板不能够被连接在一起。因为大理石上有一个模板，所以石板不能被旋转：也就是说宽高为 $A\times B$ 的石板不能被当成宽高为 $B\times A$ 的石板，除非 $A = B$。 对于所需要的任意一种尺寸的石板，Phidias 可以切出 $0$ 块或 大于 $0$ 的任意块的该种石板。当所有切割完毕时，那些与所需石板尺寸不同的石板被废弃掉。对于每种所需要的石板，他可以制作 $0$ 到多块。Phidias 需要一种切割方法使得被废弃掉的石板的总面积尽可能的小。 例如，在下图中，原始的板材为宽 $21$ 高 $11$ 的矩形，需要的石板尺寸为 $10\times 4$, $6\times2$, $7\times5$, 和 $15\times10$。 可能的最小的废弃面积为 $10$，图中给出了一种切割方法使得废弃的面积为 $10$。 写一段程序，给定原始板材的尺寸和需要的石板的尺寸，计算废弃面积的最小值。

第一行包含一个整数 $T$，表示数据组数，对于每组数据：第一行包含两个整数：第一个为 $W$ 表示原始板材的宽度，第二个为 $H$ 表示原始板材的高度。 第二行包含一个整数 $N$ 表示需要的石板的尺寸的数目。接下来的 $N$ 行包含所需石板的尺寸。其中，每行包含两个整数：第一个为宽度 $W_i$ ，第二个为高度 $H_i$。

一个整数，表示被废弃掉的石板的总面积的最小值。 **限制条件** 对于所有输入，$1 ≤ W ≤ 600, 1 ≤ H ≤ 600, 0 < N ≤ 200, 1 ≤ W_i ≤ W, 1 ≤ H_i ≤ H$, $1\le T\le 20$。 另外，对于 $50\%$ 的输入，$W ≤ 20, H ≤ 20, N ≤ 5$。