D - 救急車 (Ambulance) Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点： 100 点

IOI 王国は縦 L 行，横 L 列のマス目で表される領土を持っている．以降，上から i 行目 (1 \leqq i \leqq L)，左から j 列目 (1 \leqq j \leqq L) のマスをマス (i, j) と表すことにする．

最近の IOI 王国では感染症で倒れる患者が相次いでおり，国民から医療の充実を求める声が上がっている．そこで，IOI 王国の国王であるビ太郎は，マス (1, 1)，マス (1, L)，マス (L, 1)，マス (L, L) の 4 箇所に病院を建設し，それぞれの病院に 1 台ずつ救急車を設置することにした．

用心深いビ太郎は，実際に患者から救助要請があったときのことを想定してシミュレーションを行うことにした．ビ太郎が想定するシナリオでは，時刻 0 において N 人の患者から救助要請が届くので，時刻 T までにすべての患者をいずれかの病院に搬送することができるかどうかを調べたい．k 番目 (1 \leqq k \leqq N) の患者はマス (X_k, Y_k) にいる．

救急車は以下の規則に従って患者を搬送する．

  • それぞれの救急車は，時刻 0 以降に動き出すことができ，病院を出発し患者の存在するマスまで移動して患者を乗せ，再び病院まで移動して患者を降ろすことを繰り返す．
  • それぞれの救急車は高々 1 人の患者を乗せることができる．
  • それぞれの救急車は，その救急車が設置されている病院にしか患者を搬送することができず，病院が存在しないマスで患者を降ろしてはならない．
  • それぞれの救急車は，1 単位時間かけて上下左右いずれかに隣接するマスに移動することができ，患者を乗せるのにかかる時間および降ろすのにかかる時間は無視できる．
  • 異なる病院に設置されている救急車が同時に同じマスに存在することは可能である．

残念ながら，ビ太郎は自分の想定したシナリオの結果を調べることはできなかったため，あなたに代わりに調べるよう依頼してきた．

IOI 王国の領土の大きさおよびビ太郎が想定したシナリオの情報が与えられたとき，時刻 T までにすべての患者をいずれかの病院に搬送することができるかどうかを求めるプログラムを作成せよ．

入力

入力は以下の形式で標準入力から与えられる．

L N T
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

出力

標準出力に，ビ太郎が想定したシナリオにおいて時刻 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)．
  • 入力される値はすべて整数である．

小課題

  1. (4 点) T \leqq 50．
  2. (8 点) T \leqq 160．
  3. (5 点) N \leqq 10．
  4. (18 点) N \leqq 20．
  5. (15 点) N \leqq 45．L は奇数であり，Y_k = \frac{L+1}{2} (1 \leqq k \leqq N)．
  6. (31 点) N \leqq 45．
  7. (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 の制約を満たす．