Problem : 14 - Bugs Integrated, Inc.

Problem Statistics

Solved Member: 13　　Submission: 89　　User Tried: 17

Statement:

Bugs有限公司是生產記憶體晶片的專家，日前正以領先的技術生產6TB的超大容量記憶體晶片"Q-RAM"。每一個Q-RAM晶片都是由2*3個正方形的小單位所組成一個長方形的晶片。

你是一個在Bugs有限公司上班的員工，這家公司雖然技術領先，對員工卻意外的小器。每個員工只有發到一張二手的N*M萬用電板讓你測試記憶體晶片而已。不只如此，你還發現這張電路板是其他消費者退貨回來的不良品，N*M的格子裡面有K格是不可以用的。如上圖，我們用黑格子來表示萬用電板壞掉的部份。

身為一位稱職的員工，公司們的大家都發回勤儉持家的精神，每個人只有一塊電路板可以測試記憶體晶片。你有D位同事知道你曾經拿過IOI的金牌，因此他們想請你寫一個程式來告訴他們的電路板最多可以同時測試幾個Q-RAM晶片。

Task:

告訴你有幾位同事，以及他們電路板的大小和壞掉的情形，請你算出每位同事電路板最多可以同時測試幾個記憶體晶片。

Input:Output:

第1行有一個整數D(1<=D<=5)，代表你有幾位同事想找你測試。
接下來有D個晶片的描述，每個晶片第一行有N(1<=N<=150),M(1<=M<=10),K(0<=K<=MN)3個數字，分別代表晶片的長寬以及壞掉的格子數。
接下來有K行，每行有x(1<=x<=N),y(1<=y<=M)兩個數字，代表壞掉的格子座標。

並且電路板最左上角為(1,1)，右下角為(N,M)

對於每一個同事的測試，請你輸出1行，1個整數，代表最多可以同時測試的記憶體數量。

Sample Input:Sample Output:

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

3
4

HINT:

左右分別為範測中2個同事晶片，其中黑格子代表壞掉的地方。

Source:

CEOI 2002

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	2500ms	65536kb
1	2500ms	65536kb	10
2	2500ms	65536kb	10
3	2500ms	65536kb	10
4	2500ms	65536kb	10
5	2500ms	65536kb	10
6	2500ms	65536kb	10
7	2500ms	65536kb	10
8	2500ms	65536kb	10
9	2500ms	65536kb	10
10	2500ms	65536kb	10