题目描述

题目译自 JOISC 2025 Day2 T1 「救急車 / Ambulance」

IOI 王国拥有一片被划分为纵 $L$ 行、横 $L$ 列网格的领土。从上到下第 $i$ $(1 \leq i \leq L)$ 行、从左到右第 $j$ $(1 \leq j \leq L)$ 列的格子称为格子 $(i, j)$。

最近，IOI 王国爆发了传染病，患者接连倒下，民众纷纷呼吁加强医疗保障。为此，国王比太郎决定在领土的四个角落——格子 $(1,1)$、$(1,L)$、$(L,1)$ 和 $(L,L)$——各建一座医院，每座医院配备一辆救护车。

谨慎的比太郎想通过模拟来检验实际救援效果。他设想了一个场景：时刻 $0$ 时，$N$ 名患者同时发出求救信号，你需要判断在时刻 $T$ 前能否将所有患者送往任意一家医院。第 $k$ $(1 \leq k \leq N)$ 名患者位于格子 $(X_k, Y_k)$。

救护车的救援规则如下：

• 每辆救护车可在时刻 $0$ 后出发，从所属医院前往患者所在格子，接上患者后返回医院放下，如此反复。
• 每辆救护车最多载一名患者。
• 救护车只能将患者送回其所属医院，不得在无医院的格子放下患者。
• 救护车每次移动到上下左右相邻格子需 $1$ 单位时间，接送患者的上下车时间可忽略。
• 不同医院的救护车可同时停在同一格子。

比太郎无法自行完成模拟，便委托你代为解决。给你 IOI 王国的领土规模和比太郎的模拟场景，你需要编写程序判断在时刻 $T$ 前能否救治所有患者。

输入格式

第一行包含三个整数 $L,N,T$。

接下来的 $N$ 行，每行包含两个整数 $X_i,Y_i$。

输出格式

输出一行。若在比太郎的场景中，时刻 $T$ 前能将所有患者送往医院，输出 Yes；否则输出 No。

6 4 8
1 3
2 2
3 4
5 5

Yes

将第 $1, 2$ 名患者送往 $(1,1)$ 的医院，第 $3$ 名送往 $(1,6)$，第 $4$ 名送往 $(6,6)$，可在时刻 $8$ 前完成。例如，$(1,1)$ 的救护车按以下步骤操作：

这个样例满足子任务 $1,2,3,4,6,7$ 的限制。

9 5 19
5 5
5 5
7 5
2 5
9 5

No

时刻 $19$ 前无法救治所有患者，输出 No。

这个样例满足所有子任务的限制。

7 7 16
6 1
2 4
4 5
5 5
3 4
6 4
5 1

Yes

这个样例满足子任务 $1,2,3,4,6,7$ 的限制。

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

No

这个样例满足子任务 $4,6,7$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $3 \leq L \leq 10000$
• $1 \leq N \leq 160$
• $1 \leq T \leq 20000$
• $1 \leq X_k \leq L$ $(1 \leq k \leq N)$
• $1 \leq Y_k \leq L$ $(1 \leq k \leq N)$
• $(X_k, Y_k)$ 不是 $(1,1)$、$(1,L)$、$(L,1)$ 或 $(L,L)$ $(1 \leq k \leq N)$
• 所有输入值均为整数

详细子任务附加限制及分值如下表所示。