スタンプラリー 3 (Collecting Stamps 3)

JOI 君が住む IOI 国は，大きな湖があることで有名である．今日，湖の周りでスタンプラリー大会が行われることになった．

湖の周りには \(N\) 個のスタンプ台が設置されており，時計回りに \(1\) から \(N\) までの番号が付いている．湖の周りの長さは \(L\) メートルであり，スタンプ台 \(i\) (\(1 \leqq i \leqq N\)) はスタンプラリーのスタート地点から湖の周りに沿って時計回りに \(X_i\) メートルだけ進んだ地点に設置されている．

スタンプラリーの各参加者は，スタンプラリー開始時にはスタート地点にいて，スタンプラリー開始後は湖の周りに沿って時計回りもしくは反時計回りに移動することができる．参加者は，スタンプ台が設置されている地点に到着したとき，まだそのスタンプ台でスタンプを押していなかった場合に限り，スタンプを \(1\) 回だけ押すことができる．ただし，スタンプ台 \(i\) (\(1 \leqq i \leqq N\)) はスタンプラリー開始から \(T_i\) 秒が経過すると撤去され，それより後に参加者が到着してもそのスタンプ台でスタンプを押すことはできなくなる．なお，\(T_i\) 秒ちょうどに参加者が到着した場合については，スタンプを押すことができるとする．

JOI 君はこのスタンプラリー大会の参加者である．JOI 君は \(1\) メートルを進むのに \(1\) 秒かかる．また，JOI 君はスタンプを押すことに熟練しているので，スタンプを押すのにかかる時間は無視することができる．

スタンプ台の個数，湖の周りの長さ，各スタンプ台が設置されている地点，各スタンプ台が撤去される時刻が与えられたとき，JOI 君が押すことのできるスタンプの個数の最大値を求めるプログラムを作成せよ．

入力は以下の形式で標準入力から与えられる．入力される値はすべて整数である．

\(N\) \(L\)
\(X_1\) \(\cdots\) \(X_N\)
\(T_1\) \(\cdots\) \(T_N\)

JOI 君が押すことのできるスタンプの個数の最大値を，標準出力に \(1\) 行で出力せよ．

• \(1 \leqq N \leqq 200\)．
• \(2 \leqq L \leqq 1\,000\,000\,000\)．
• \(1 \leqq X_i < L\) (\(1 \leqq i \leqq N\))．
• \(X_i < X_{i+1}\) (\(1 \leqq i \leqq N - 1\))．
• \(0 \leqq T_i \leqq 1\,000\,000\,000\) (\(1 \leqq i \leqq N\))．

1. (\(5\) 点) \(N \leqq 12\)，\(L \leqq 200\)，\(T_i \leqq 200\) (\(1 \leqq i \leqq N\))．
2. (\(10\) 点) \(N \leqq 15\)．
3. (\(10\) 点) \(L \leqq 200\)，\(T_i \leqq 200\) (\(1 \leqq i \leqq N\))．
4. (\(75\) 点) 追加の制約はない．

JOI 2020 · JCIOI · CC BY-SA 4.0