TopCoder

User's AC Ratio

87.5% (7/8)

Submission's AC Ratio

45.0% (9/20)

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

No. Testdata Range Score
1 0 9
2 1 9
3 2 9
4 3 9
5 4 9
6 5 9
7 6 9
8 7 9
9 8 9
10 9 9
11 10 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2000 65536 262144 1
1 2000 65536 262144 2
2 2000 65536 262144 3
3 2000 65536 262144 4
4 2000 65536 262144 5
5 2000 65536 262144 6
6 2000 65536 262144 7
7 2000 65536 262144 8
8 2000 65536 262144 9
9 2000 65536 262144 10
10 2000 65536 262144 11