配点: 100 点
IOI王国是垂直的 L 行,横 L 它有一个由一列方块表示的领土。从此,从上往下 i 行目 (1 \leqq i \leqq L),从左起 j 列目 (1 \leqq j \leqq L) 它被称为 (i, j) 。
近期,IOI王国出现多位患者因传染病倒地的情况,民众呼吁改善医疗状况。所以,IOI王国的国王Bitaro, (1, 1),质量 (1, L),质量 (L, 1),质量 (L, L) 的 已知 4 在每个地点建造一所医院并 1 我们决定一次安装一辆救护车。
出于谨慎,Bitaro 决定根据患者实际请求帮助时会发生的情况进行模拟。在 Bitaro 设想的场景中,时间 在 0 中 N 收到多名患者的救援请求,所以时间 我们想了解是否所有患者都可以通过 T 运送到任何医院。k 番目 (1 \leqq k \leqq N) 患者数量众多 我在 (X_k, Y_k) 。
救护车根据以下规则运送患者。
- 每辆救护车 0 之后,你可以开始移动,离开医院,移动到病人所在的广场,接病人,再次移动到医院,放下病人,重复这个过程。
- 每辆救护车最多有 1 可承载多名患者。
- 每辆救护车只能将病人运送到该救护车所在的医院,不得在没有医院的广场下车。
- 每辆救护车都是1 上下左右移动到相邻的方格需要一个时间单位,接送病人的时间可以忽略不计。
- 安装在不同医院的救护车有可能同时存在于同一个广场。
不幸的是,Bitaro 无法调查他假设场景的结果,因此他要求你代表他进行调查。
IOI 考虑到王国领土的大小和Bitaro假设的场景,时间 编写一个程序来查明是否所有患者都可以通过 T 运送到任何医院。
入力
输入是按以下格式从标准输入给出的。
L N T X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
出力
标准输出显示 Bitaro 假设场景中的时间。
如果所有患者都可以通过 T 运送到医院 Yes ,否则
在 No 分成 1 行输出。
没有
制約
- 3 \leqq L \leqq 10\, 000.
- 1 \leqq N \leqq 160.
- 1 \leqq T \leqq 20\, 000.
- 1 \leqq X_k \leqq L (1 \leqq k \leqq N)
- 1 \leqq Y_k \leqq L (1 \leqq k \leqq N)
- (X_k, Y_k) 为 (1, 1), (1, L), (L, 1), (L, L) (1 \leqq k \leqq N).
- 所有输入值均为整数。
小課題
- (4 点) T \leqq 50.
- (8 点) T \leqq 160.
- (5 点) N \leqq 10.
- (18 点) N \leqq 20.
- (15 点) N \leqq 45.L 是奇数, 肿块Y_k = \frac{L+1}{2} (1 \leqq k \leqq N).
- (31 点) N \leqq 45.
- (19 点)没有额外的限制。
入力例 1
6 4 8 1 3 2 2 3 4 5 5
出力例 1
Yes
1 第 和
第 2 患者
去 (1, 1) 医院,3 患者
去 (1, 6) 医院,4 患者
去 (6, 6) 由于所有患者都可以通过 8 运送到其中一家医院,Yes 。
例如,质量 当 (1, 1) 的医院安装的救护车按以下顺序移动时,该救护车 通过 8 第 1 第 和 第 2 号患者可以被送往医院。
| 時刻 | 救护车状态 离开 |
|---|---|
| 0 | 质量 由 (1, 1) 到达 |
| 1 | 质量 由 (2, 1) 到达 |
| 2 | 质量 由 (2, 2) , 接起2 病人并离开。 |
| 3 | 质量 由 (1, 2) 到达 |
| 4 | 质量 由 (1, 1) , 接起2 送病人离开 |
| 5 | 质量 由 (1, 2) 到达 |
| 6 | 质量 由 (1, 3) , 接起1 病人并离开。 |
| 7 | 质量 由 (1, 2) 到达 |
| 8 | 质量 由 (1, 1) , 接起1 卸载病人 由于 |
此输入示例是一个小作业。 1,2,3,4,6,7 满足约束。 如果设置为
入力例 2
9 5 19 5 5 5 5 7 5 2 5 9 5
出力例 2
No
時刻 19 不可能将所有患者运送到任何医院,No 。
此输入示例满足所有子任务约束。
入力例 3
7 7 16 6 1 2 4 4 5 5 5 3 4 6 4 5 1
出力例 3
Yes
此输入示例是一个小作业。 1,2,3,4,6,7 满足约束。 如果设置为
入力例 4
200 15 800 126 45 196 40 43 58 96 13 28 33 44 55 60 22 58 156 135 183 44 29 92 182 157 138 30 132 175 87 166 57
出力例 4
No
此输入示例是一个小作业。 4,6,7 满足约束。 如果设置为