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

JOI 君が住むIOI 国は,大きな湖があることで有名である.今日,湖の周りでスタンプラリー大会が行
われることになった.
湖の周りにはN 個のスタンプ台が設置されており,時計回りに1 からN までの番号が付いている.湖の
周りの長さはL メートルであり,スタンプ台i (1 ≦i ≦N) はスタンプラリーのスタート地点から湖の周り
に沿って時計回りにXi メートルだけ進んだ地点に設置されている.
スタンプラリーの各参加者は,スタンプラリー開始時にはスタート地点にいて,スタンプラリー開始後
は湖の周りに沿って時計回りもしくは反時計回りに移動することができる.参加者は,スタンプ台が設置
されている地点に到着したとき,まだそのスタンプ台でスタンプを押していなかった場合に限り,スタン
プを1 回だけ押すことができる.ただし,スタンプ台i (1 ≦i ≦N) はスタンプラリー開始からTi 秒が経過
すると撤去され,それより後に参加者が到着してもそのスタンプ台でスタンプを押すことはできなくなる.
なお,Ti 秒ちょうどに参加者が到着した場合については,スタンプを押すことができるとする.
JOI 君はこのスタンプラリー大会の参加者である.JOI 君は1 メートルを進むのに1 秒かかる.また,JOI
君はスタンプを押すことに熟練しているので,スタンプを押すのにかかる時間は無視することができる.
スタンプ台の個数,湖の周りの長さ,各スタンプ台が設置されている地点,各スタンプ台が撤去される時
刻が与えられたとき,JOI 君が押すことのできるスタンプの個数の最大値を求めるプログラムを作成せよ.

• 1 ≦N ≦200.
• 2 ≦L ≦1 000 000 000.
• 1 ≦Xi < L (1 ≦i ≦N).

第19 回日本情報オリンピック(JOI 2019/2020) 本選
2020 年2 月9 日(茨城県つくば市)
• Xi < Xi+1 (1 ≦i ≦N −1).
• 0 ≦Ti ≦1 000 000 000 (1 ≦i ≦N).

1. (5 点) N ≦12,L ≦200,Ti ≦200 (1 ≦i ≦N).
2. (10 点) N ≦15.
3. (10 点) L ≦200,Ti ≦200 (1 ≦i ≦N).
4. (75 点) 追加の制約はない.

入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.
N L
X1 . . . XN
T1 . . . TN

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

생성자가 기록되지 않았습니다.

출처 JOI 2020 Final