No.274 The Wall

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 125
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm
3 ProblemId : 658 / 出題時の順位表

問題文

$1 \times 1$のブロックが横に$M個$連なった$1 \times M$のブロックがある。
ブロックは基本白色であるが左からL番目から左からR番目(0-index)までの連続したブロックはピンク色である。
ブロックは180度回転することもできる(90度回転はできません)。
すなわち、以下の図のようなものである。



横の長さが同じ$1 \times M$のN本のブロックが与えられる。
それぞれのブロックはそれぞれピンク色の連続した領域を1つ持つ。
N本のブロックを上に積んでいき良い壁を作りたい。
良い壁とは縦の列でブロックを見たときピンク色のブロックが1つ以下のものをいう。

例えば、$1 \times 6$のブロックを4つ積んだときの良い壁と悪い壁の例。


左の壁は縦にブロックを見たときにピンク色のブロックが無いか1つのピンク色のブロックがある良い壁である。
一方、右の壁は縦で見たときピンク色のブロックが2つ以上ある場合があり悪い壁である。

いずれのブロックにも180度回転を好きなだけ行うことができる。
与えられるN本のブロックをすべて積んで良い壁を作れるか判定せよ。

入力

$N$ $M$
$L_0$ $R_0$
$L_1$ $R_1$
$ \vdots\ $
$L_{N-1}$ $R_{N-1}$

$N$は$1 \times M$のブロックの本数。$2\le N \le 2000$。
$M$は1本のブロックの横のブロック数。$2\le M \le 4000$。
$L_i$は$i$番目のブロックのピンク領域の最左のブロック位置。
$R_i$は$i$番目のブロックのピンク領域の最右のブロック位置。
$0\le L_i \le R_i \le {M-1}$。

出力

良い壁ができる時には"YES" 、できないときには"NO"を1行で出力してください。
最後に改行してください。

サンプル

サンプル1
入力
4 6
5 5
2 3
4 4
1 1
出力
YES

問題文中の良い壁の例と同じ。
どのブロックも180度回転させずに積めば良い壁になる。
0番目のブロックを180度回転させても良い壁には変わりない。

サンプル2
入力
4 6
3 5
3 4
4 4
1 2
出力
NO

問題文中の悪い壁の例と同じ。
180度回転をどのように使っても良い壁はできない。

サンプル3
入力
2 4
0 1
0 1
出力
YES

どちらかのブロックを180度回転させて積めば良い壁になる。

サンプル4
入力
5 10
8 8
0 0
2 4
2 3
8 8
出力
YES

良い壁にできます。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。