IOI 王国拥有一个由 $L$ 行 $L$ 列排列的方格组成的领土。从上往下第 $i$ 行（$1 \leq i \leq L$）、从左往右第 $j$ 列（$1 \leq j \leq L$）的格子记作 $(i,j)$。

最近，IOI 王国出现了许多因传染病倒下的患者，民众呼吁加强医疗设施。因此，IOI 王国的国王“比太郎”决定在 $(1, 1)$、$(1, L)$、$(L, 1)$、$(L, L)$ 这四个位置各建一座医院，并为每家医院配备一辆救护车。

谨慎的比太郎打算模拟实际发生救援请求时的情况。设想的场景是，时刻 $0$ 时有 $N$ 位患者发出救援请求，他想知道能否在时刻 $T$ 之前将所有患者都送到任意一家医院。第 $k$ ($1 \leq k \leq N$) 位患者位于 $(X_k, Y_k)$。

救护车按如下规则运送患者：

• 每辆救护车可在时刻 $0$ 之后出发，从对应医院出发到达患者所在格，搭载患者返回医院后，继续接送下一位病人。
• 每辆救护车一次最多只能搭载一位患者。
• 每辆救护车只能将患者运送回其对应医院，不能在其他无医院的格子卸下患者。
• 每辆救护车每次在上下左右相邻的格之间移动需要 $1$ 单位时间，搭载和卸下患者消耗的时间可忽略不计。
• 不同医院的救护车可以同时停留在同一个格子内。

由于比太郎无法得知自己设想场景的最终结果，因此请你编程帮他判断，在给定的领土大小和场景条件下，是否可以在时刻 $T$ 之前将所有患者送到任一医院。

输入通过标准输入给出，格式如下：

$L$ $N$ $T$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_N$ $Y_N$

如果比太郎预想的场景下，能在时刻 $T$ 之前将所有患者送到任意一家医院，输出 Yes，否则输出 No，输出占一行。

子任务

1.（$5$ 分）$T \leq 50$。
2.（$10$ 分）$T \leq 160$。
3.（$8$ 分）$N \leq 10$。
4.（$21$ 分）$N \leq 20$。
5.（$17$ 分）$N \leq 45$，$L$ 为奇数且 $Y_k = \frac{L+1}{2}$（$1 \leq k \leq N$）。
6.（$29$ 分）$N \leq 45$。
7.（$10$ 分）没有额外约束。

---

样例解释1

可以将第 $1$、$2$ 位患者送到 $(1,1)$ 的医院，第 $3$ 位送到 $(1,L)$ 的医院，第 $4$ 位送到 $(L,L)$ 的医院，在时刻 $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

无法在时刻 $19$ 之前将所有患者送达任意一家医院，因此输出 No。

本样例满足全部子任务约束。

---

样例解释3

本样例满足子任务 $1,2,3,4,6,7$ 的约束。

---

样例解释4

本样例满足子任务 $4,6,7$ 的约束。

约束条件

• $3 \leq L \leq 10,000$。
• $1 \leq N \leq 160$。
• $1 \leq T \leq 20,000$。
• $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$）。
• 所有输入均为整数。

由 ChatGPT 5 翻译