34106번 - Ambulance 서브태스크다국어

The IOI Kingdom is represented as a square grid of $L$ rows and $L$ columns. The rows are numbered $1, 2, \dots , L$ from top to bottom and the columns are numbered $1, 2, \dots , L$ from left to right. A cell at row $i$ ($1 ≤ i ≤ L$) and column $j$ ($1 ≤ j ≤ L$) is denoted as cell $(i, j)$.

Recently, due to a widespread infection in the IOI Kingdom, the demand for improved medical facilities has increased. In response, the king, Bitaro, has decided to build hospitals in the four corners of the grid, which are cell $(1, 1)$, cell $(1, L)$, cell $(L, 1)$, and cell $(L, L)$. Each hospital is equipped with one ambulance.

The cautious Bitaro decided to run a simulation to prepare for actual emergency calls from patients. In the scenario he envisioned, emergency calls from $N$ patients arrive at time $0$, and he wants to determine whether all patients can be transported to one of the hospitals by time $T$. The $k$-th patient ($1 ≤ k ≤ N$) is located at cell $(X_k, Y_k)$.

The ambulances transport patients according to the following rules:

• Each ambulance can start moving at time $0$ or later. It repeats the following (possibly $0$ times): depart from its hospital, move to the patient’s location, pick up the patient, and then return to the hospital to drop off the patient.
• Each ambulance can carry at most $1$ patient at a time.
• Each ambulance can only transport patients to the hospital where it was initially stationed. Patients cannot be dropped off at any location other than a hospital.
• Each ambulance moves to an adjacent cell (up, down, left, or right) in $1$ unit of time. The time taken to pick up and drop off a patient can be ignored.
• Ambulances from different hospitals may occupy the same cell at the same time.

Unfortunately, Bitaro was unable to determine the outcome of his envisioned scenario, so he has asked you to investigate it on his behalf.

Given the size of the IOI Kingdom and the scenario envisioned by Bitaro, write a program to determine whether all patients can be transported to a hospital by time $T$.

The input is given from Standard Input in the following format:

$L$ $N$ $T$

$X_1$ $Y_1$

$X_2$ $Y_2$

$\vdots$

$X_N$ $Y_N$

Print Yes if all patients can be transported to a hospital by time $T$ in the scenario envisioned by Bitaro. Otherwise, print No. The output should consist of a single line.

• $3 ≤ L ≤ 10\, 000$.
• $1 ≤ N ≤ 160$.
• $1 ≤ T ≤ 20\, 000$.
• $1 ≤ X_k ≤ L$ ($1 ≤ k ≤ N$)
• $1 ≤ Y_k ≤ L$ ($1 ≤ k ≤ N$)
• $(X_k, Y_k)$ is not equal to any of $(1, 1)$, $(1, L)$, $(L, 1)$, or $(L, L)$. ($1 ≤ k ≤ N$)
• All input values are integers.