TopCoder

User's AC Ratio

100.0% (5/5)

Submission's AC Ratio

71.4% (5/7)

Description

你是一名強大的工程師,

最近你的公司生產了一種 2 x 3 單位尺寸的高科技晶片,

晶片將被嵌入 n x m 單位尺寸的矩形晶圓內,但在生產晶圓原體的時候難免會有損壞的情況發生,

所以在經過嚴格的檢查之後,你在損壞的單位小方格內標上了黑色記號(見上圖)

而為了要保持晶片的良好運作,放置晶片的地方不能有損壞,晶片之間也不能互相重疊。

為了節省成本,公司希望將盡量多的晶片嵌入晶圓內,所以請你求出可能的最大晶片數量。

Input Format

本題有多筆測試資料:

第一行包含一個數字 T,代表有幾張晶圓需要你判斷。

每筆資料的:

第一行有三個數字,n, m, k,代表你的晶圓是 n x m 的,而其中有 k 格有損壞的情形。(1 <= n <= 500,1 <= m <= 10,k <= mn)

接下來有 k 行,每行有兩格數字 x,y 代表損壞位置的座標(1 <= x <= n, 1 <= y <= m)

Output Format

對於每筆測試資料輸出一個數字 x ,代表最多可以嵌入 x 張晶片。

Sample Input

2
6 6 5
1 4
4 6
2 2
3 6
6 4
6 5 4
3 3
6 1
6 2
6 4

Sample Output

3
4

Hints

Problem Source

原TIOJ1468 / 建中校內培訓第四次模擬考試。
Problem Setter:hallogameboy、peter50216
(Adapt From:CEOI 2002)

Subtasks

For Testdata: 0 ~ 0, Score: 9
For Testdata: 1 ~ 1, Score: 9
For Testdata: 2 ~ 2, Score: 9
For Testdata: 3 ~ 3, Score: 9
For Testdata: 4 ~ 4, Score: 9
For Testdata: 5 ~ 5, Score: 9
For Testdata: 6 ~ 6, Score: 9
For Testdata: 7 ~ 7, Score: 9
For Testdata: 8 ~ 8, Score: 9
For Testdata: 9 ~ 9, Score: 9
For Testdata: 10 ~ 10, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 60000 65536 65536
1 60000 65536 65536
2 60000 65536 65536
3 60000 65536 65536
4 60000 65536 65536
5 60000 65536 65536
6 60000 65536 65536
7 60000 65536 65536
8 60000 65536 65536
9 60000 65536 65536
10 60000 65536 65536