1368: #2372. 「CEOI2002」臭虫集成电路公司

Memory Limit:8 MB Time Limit:10.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

臭虫集成电路公司是我国先端内存芯片的主要供应厂商。他们新投产了一种 6TB 的 Q-RAM 芯片,每块这种芯片可以表示为 2×32 \times 32×3 的矩形。 Q-RAM 芯片是从一块 N×MN \times MN×MN×MN \times MN×M 大小的硅片上切下来的,但由于臭虫王国的半导体技术不够发达,产品的原料经常不够纯,因而有若干的单位正方形并不能作为芯片的一部分。

臭虫集成电路公司想要知道,给定一块 N×MN \times MN×M 大小的硅片和原料不纯的单位正方形的位置,最多能使用这块硅片生产多少 Q-RAM 芯片。

输入格式

输入的第一行由一个正整数 DDD 构成,表示硅片的个数。

随后跟着 DDD 个数据,每个数据第一行包含三个整数 NNNMMMKKK,分别表示硅片的长和宽,以及硅片原料不纯的单位正方形个数。接下 KKK 行,每行两个整数 XXXYYY ,表示单位正方形的坐标。(左上角的单位正方形用 (1,1)(1,1)(1,1) 表示,右下角的单位正方形用 (N,M)(N,M)(N,M) 表示。)

输出格式

DDD 行,每行一个整数,即最多能切出多少个 Q-RAM 芯片。

样例

样例输入

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

数据范围与提示

共有 101010 个测试点,测试点间独立计分。

对于 10%10 \%10% 的数据(测试点 #10),有 K=0K = 0K=0
对于另 10%10 \%10% 的数据(测试点 #4),有 D=1, K=1D = 1, \ K = 1D=1, K=1
对于另 10%10 \%10% 的数据(测试点 #1),有 K≤1K \leq 1K1
对于所有数据,1≤D≤5 1 \leq D \leq 5 1D51≤N≤150 1 \leq N \leq 150 1N1501≤M≤10 1 \leq M \leq 10 1M100≤K≤MN 0 \leq K \leq MN 0KMN

请注意内存和时间限制。