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

内存限制:8 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: luyanaa

题目描述

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

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

输入格式

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

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

输出格式

D 行,每行一个整数,即最多能切出多少个 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

数据范围与提示

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

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

请注意内存和时间限制。