#1046. 躲避滚石

内存限制:512 MiB 时间限制:1000 ms 输入文件:rock.in 输出文件:rock.out
题目类型:传统 评测方式:文本比较
上传者: H6_6Q

题目描述

小P 在玩躲避滚石游戏。

游戏中有 n 条道路,每条道路都有 m 个单位位置。

在这 n 条路上,有 p 个滚石,这些滚石会以每秒走 k 个单位的速度从第 m 个单位位置向第 1 个单位位置的方向滚去,当一个滚石移动出道路时,我们认为这个滚石被躲避。

现在 小P 可以从这些道路中任何一条的第 1 个单位位置开始躲避滚石。而在每一秒滚石移动之前,他都有一次移动到相邻道路或不动的机会。

如果 小P 能躲避所有的滚石,那么他就能胜利。

在任何时刻(单位不一定是秒),小P 都不能与滚石处在同一个位置。

请你告诉 小P 是否存在任意一种能够胜利的躲避方案。

输入格式

第一行输入一个整数 t ,表示一共有多少组数据。

对于每组数据:

先输入四个整数 n,m,k,p ,含义如上。

接下来 p 行,每行输入两个数 x_i,y_i 表示第 i 个滚石刚开始在第 x_i 条道路的第 y_i 个单位位置。

输出格式

对于每组数据:

如果存在一种可以使 小P 胜利的移动方案,输出 Yes

否则输出 No

样例

输入样例 #1:

2
3 5 1 3
1 2
2 3
3 5
3 5 1 3
1 2
2 2
3 2

输出样例 #1:

Yes
No

数据范围与提示

【样例解释】

对于样例 #1 中的第一组数据:

小P 可以通过:不动 —— 不动 —— 不动 —— 移动到第 2 条道路 —— 不动 来获得胜利

【数据范围】

对于 30\% 的数据,满足 n=2 , m \le 10

对于另外 30\% 的数据,满足 n,m \le 10

对于另外 20\% 的数据,满足 n,m \le 100

对于全部数据,满足 1 \le n,m \le 1000 , 1 \le x \le n , 2 \le y_i \le m , 1 \le k \le m , 1 \le t \le 10