Problem : 253 - Phidias

Problem Statistics

Solved Member: 15　　Submission: 18　　User Tried: 15

Statement:

有名的希臘雕刻神菲迪亞斯正在為他下一座雄偉的雕像作準備。為了這座雕像他需要大小為W₁×H₁, W₂×H₂, ..., W_N ×H_N 的矩形大理石板。

最近菲迪亞斯獲得一塊矩形大理石塊。菲迪亞斯想把這塊石板切成所需要的大小。石板或是石板所切割出的部分都可以由垂直(或水平)方向縱貫(或是橫貫)加以切割到底，成兩塊矩形石板，同時切割出的這兩塊矩形石板都必須具有整數的寬度與高度。石板只能以此種方法加以切割，同時石板不能粘合成較大石板。因為石板具有花紋，所以石板也不能旋轉。如果菲迪亞斯切割出一塊A×B 的石板，則此石板不能被當成B×A 的石板使用，除非A 等於B。對每一種所需石板大小菲迪亞斯可切割出零或更多塊石板。如果當所有的切割完成時，一塊產生出的石板並不是任何所需要的大小，則此石板成為廢料。菲迪亞斯想知道如何切割最初的石板，讓所產生的廢料最少。

舉例來說，下圖中的原始石板寬度為 21 且高度為 11，而所需石板大小為10×4,6×2, 7×5 及15×10, 則最小廢料總面積為 10。下圖同時畫出最小廢料總面積為10 的切割方法。

你的工作是寫一個程式由給定的原始石板大小及所需要的各種石板大小計算出最小的廢料總面積。

Input:Output:

第一行為兩個整數。第一個整數 W 為原始石板的寬度，第二個整數 H 為原始石板的高度。輸入檔第二行為一個整數 N，代表所需石板種類數目。以下 N 行為各種所需石板的大小。每一行為兩個整數，第一個整數為所需石板寬度 Wi，第二個整數為所需石板寬度 Wi (1 ≤ i ≤ N)。

在所有的輸入中，1 ≤ W ≤ 600, 1 ≤ H ≤ 600, 0 ≤ N ≤ 200, 1 ≤ Wi ≤ W，並且1 ≤ Hi ≤ H。除此之外，在50%的輸入檔中，W ≤ 20, H ≤ 20 並且N ≤ 5。

輸出為一行且僅包含一個整數，代表最小廢料總面積。

Sample Input:Sample Output:

21 11
4
10 4
6 2
7 5
15 10

Source:

IOI 2004

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	1000ms	16384kb
1	1000ms	16384kb	5
2	1000ms	16384kb	5
3	1000ms	16384kb	5
4	1000ms	16384kb	5
5	1000ms	16384kb	5
6	1000ms	16384kb	5
7	1000ms	16384kb	5
8	1000ms	16384kb	5
9	1000ms	16384kb	5
10	1000ms	16384kb	5
11	1000ms	16384kb	5
12	1000ms	16384kb	5
13	1000ms	16384kb	5
14	1000ms	16384kb	5
15	1000ms	16384kb	5
16	1000ms	16384kb	5
17	1000ms	16384kb	5
18	1000ms	16384kb	5
19	1000ms	16384kb	5
20	1000ms	16384kb	5