TopCoder

Thumb rezero
Re Zero
Re Zero

User's AC Ratio

100.0% (6/6)

Submission's AC Ratio

45.5% (10/22)

Tags

Description

mac開了一家"好多BUG公司",而這家公司專門生產6bit的Mac晶片,每塊Mac晶片都是由2*3的小mac組成的。
生產晶片的方法如下:
將一個MacBroad劃分為N*M塊,即N行,M列。這些小塊都經過了仔細的測試並給標記了黑色記號。
最後,將每塊2*3的小mac鑲嵌在N*M的MacBroad上,要求:
1.每塊小mac都放在MacBroad的六個格子裡,且各塊之間不能重疊。
2.小mac不允許鑲嵌在黑色記號上。

給出資料,輸出能放置小晶片的最大個數。

Input Format

第一行,一個整數D(1<=D<=5),為測試資料的個數。
第二行,三個數N(1<=N<=150), M(1 <= M <= 10), K(0 <= K <= MN),分別為矽晶片的行數,列數,和黑色記號數量。
接下來的K行,為無效塊在矽晶片中的位置(the upper left square has coordinates [1, 1], the bottom right is [N,M])。

詳細請看範測

Output Format

輸出D行,每行一個你認為是答案的整數。

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

你的Mac太多了,該換ALO了歐>.O

Problem Source

Subtasks

No. Testdata Range Score
1 0~10 100

Testdata and Limits

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