AT_abc327_f [ABC327F] Apples

[problemUrl]: https://atcoder.jp/contests/abc327/tasks/abc327_f 数直線上にりんごの木が並んでおり、 $ N $ 個のりんごが木から落ちてきます。 具体的には $ 1\leq\ i\leq\ N $ について、時刻 $ T_i $ に座標 $ X_i $ にりんごが落ちてきます。 高橋君は耐久性が $ D $ , 長さ $ W $ のカゴを持っており、**一度だけ** 次の行動を取ることができます。 > 正整数 $ S $, $ L $ を選ぶ。高橋君は時刻 $ S-0.5 $ に $ L-0.5\leq\ x\leq\ L+W-0.5 $ の範囲を覆うようにカゴを設置し、時刻 $ S+D-0.5 $ に回収する。 高橋君はカゴを設置してから回収するまでの間に、カゴが設置されていた範囲に落ちてきたりんごをすべて得ることができる。 高橋君は一度設置したカゴを動かしたり、回収したカゴを再度設置することはできません。 高橋君が得られるりんごの数の最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ D $ $ W $ $ T_1 $ $ X_1 $ $ T_2 $ $ X_2 $ $ \vdots $ $ T_N $ $ X_N $

高橋君が得られるりんごの数の最大値を出力せよ。

### 制約 - $ 1\ \leq\ N\leq\ 2\times\ 10^5 $ - $ 1\ \leq\ D\leq\ 2\times\ 10^5 $ - $ 1\ \leq\ W\leq\ 2\times\ 10^5 $ - $ 1\ \leq\ T_i\leq\ 2\times\ 10^5 $ - $ 1\ \leq\ X_i\leq\ 2\times\ 10^5 $ - $ (T_i,X_i) $ はすべて異なる。 - 入力はすべて整数 ### Sample Explanation 1 高橋君は $ S=3 $, $ L=2 $ を選ぶと、時刻 $ 2.5 $ から $ 6.5 $ までカゴを $ 1.5\leq\ x\leq\ 4.5 $ の範囲に設置します。このとき、 - 時刻 $ T_2=3 $ に 座標 $ X_2=4 $ に落ちてくるりんご - 時刻 $ T_3=6 $ に 座標 $ X_3=4 $ に落ちてくるりんご - 時刻 $ T_4=5 $ に 座標 $ X_4=2 $ に落ちてくるりんご - 時刻 $ T_5=4 $ に 座標 $ X_5=2 $ に落ちてくるりんご - 時刻 $ T_6=4 $ に 座標 $ X_6=3 $ に落ちてくるりんご の $ 5 $ 個のりんごを得ることができます。 どのように行動しても $ 6 $ 個以上のりんごを得ることはできないため、$ 5 $ を出力します。