2942. 雷电

单点时限: 2.0 sec

内存限制: 256 MB

CY 很喜欢玩游戏,尤其是经典的游戏。前一段时间,CY 特迷雷电系列游戏,经常在空闲的时候对着电脑玩,可是由于技术有限,常常连第一关的 BOSS 都没见到就 GAME OVER 了 ……. 这样 n 次以后,CY 真的要抓狂了,于是,他大声喊出:“ 我要无敌!!。”

由于不能改变下载下来的游戏,CY 自己写一个雷电,在他的雷电里,玩家的飞机是无敌的。“ 撞碎一切敌机 ”,这就是他的宗旨,因此没有子弹的存在。游戏的屏幕可以看成一个 m 行 n 列的小正方形组成(编号分别是 1 到 m 行,1 到 n 列)。CY 的飞机在第 m 行,只能左右移动到相邻的格子,且消耗 1 单位时间,飞机不能飞出屏幕。整个游戏一共进行 t+m 单位时间,出现 k 架敌机,且敌机从第 1 行进入屏幕,同 1 列同一时刻可能出现多架敌机。敌机只能向下移动,且每移动一个消耗 1 单位时间。时刻 0,CY 的飞机在第 m 行第 1 列处。

虽然说 CY 已经无敌了,但是他仍想更多地摧毁敌机来泄愤,请你写一个程序帮助 CY 计算出他做多撞毁多少架敌机。

输入格式

第 1 行是一个整数 T 表示测试数据组数

接下来是 T 组测试数据,对于每组数据:

第 1 行为题目描述中的 n, m, t, k(1 <= n <= 10, 1 <= m <= 10, 1 <= t <= 10000, 0 <= k <= 10000 )

接下来有 k 行,每行有两个整数 ti, li( 1 <= ti <= t, 1 <= li <= n ) 表示在 ti 时刻,在第 1 行第 li 列出现了敌机。

输出格式

对于每组测试数据,输出 1 行,表示 CY 最多能摧毁的敌机数量。

样例

Input
1
3 3 4 3
1 1
2 2
2 3
Output
2

23 人解决,28 人已尝试。

31 份提交通过,共有 99 份提交。

4.5 EMB 奖励。

创建: 8 年,3 月前.

修改: 2 年,7 月前.

最后提交: 4 月前.

来源: ECNU 2011 ACM/ICPC Selective Trials

题目标签