AT_agc075_b [AGC075B] Traffic Light

ある信号があります。この信号は常に赤になっていますが、PCT 君が $ P $ 円払ってボタンを押すと $ X $ 秒間緑になります。ただし、PCT 君は以下のルールを守る必要があります。 - ボタンを押すことが出来るのは整数 $ t $ に対して時刻 $ t $ と表すことが出来るタイミングのみ。( $ t $ として負の整数を選ぶことも出来ます。) - 時刻 $ t $ にボタンを押した場合、時刻 $ t+Y $ になるまでボタンを押すことはできない。(時刻 $ t+Y $ にボタンを押すことは可能です。) この信号を $ N $ 人の人が渡ろうとしています。 $ i $ 人目の人は時刻 $ A_i + 0.5 $ にこの信号を渡ろうとしていて、時刻 $ A_i + 0.5 $ に信号が緑だと PCT 君に $ C_i $ 円を払います。 (PCT 君の貰ったお金 $ - $ ボタンを押すためにかかった費用) としてあり得る最大値を求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて解いてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各ケースは以下の形式で与えられる。 > $ N $ $ P $ $ X $ $ Y $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $ $ C_1 $ $ C_2 $ $ \dots $ $ C_N $

$ T $ 行出力せよ。 $ i(1 \le i \le T) $ 行目には $ \mathrm{case}_i $ の答えを出力せよ。

### Sample Explanation 1 $ 1 $ 個目のテストケースについて、PCT 君の行動例として、以下のようなものがあります。 - $ 4 $ 円払い、時刻 $ -1 $ にボタンを押す。これにより時刻 $ -1 $ から時刻 $ 4 $ の間信号が緑になる。 - 時刻 $ 3.5 $ に人 $ 1 $ が来る。信号が緑なので PCT 君に $ 6 $ 円を払う。 - 時刻 $ 5.5 $ に人 $ 2 $ が来る。信号が赤なので何もしない。 - $ 4 $ 円払い、時刻 $ 11 $ にボタンを押す。これにより時刻 $ 11 $ から時刻 $ 16 $ の間信号が緑になる。 - 時刻 $ 11.5 $ に人 $ 3 $ が来る。信号が緑なので PCT 君に $ 9 $ 円を払う。 この場合、(PCT 君の貰ったお金 $ - $ ボタンを押すためにかかった費用) は $ 7 $ 円となり、かつ $ 7 $ 円が最大値であることが証明できます。 $ 2 $ 個目のテストケースについて、PCT 君の行動例として、以下のようなものがあります。 - $ 2 $ 円払い、時刻 $ 1 $ にボタンを押す。これにより時刻 $ 1 $ から時刻 $ 2 $ の間信号が緑になる。 - 時刻 $ 1.5 $ に人 $ 1 $ が来る。信号が緑なので PCT 君に $ 100 $ 円を払う。 - $ 2 $ 円払い、時刻 $ 2 $ にボタンを押す。これにより時刻 $ 2 $ から時刻 $ 3 $ の間信号が緑になる。 - 時刻 $ 2.5 $ に人 $ 1 $ が来る。信号が緑なので PCT 君に $ 100 $ 円を払う。 - $ 2 $ 円払い、時刻 $ 3 $ にボタンを押す。これにより時刻 $ 3 $ から時刻 $ 4 $ の間信号が緑になる。 - 時刻 $ 3.5 $ に人 $ 1 $ が来る。信号が緑なので PCT 君に $ 100 $ 円を払う。 この場合、(PCT 君の貰ったお金 $ - $ ボタンを押すためにかかった費用) は $ 294 $ 円となり、かつ $ 294 $ 円が最大値であることが証明できます。 PCT 君は負の時刻にもボタンを押すことが出来ることに注意してください。 ### Constraints - $ 1 \le T \le 2 \times 10^5 $ - $ 1 \le N \le 2 \times 10^5 $ - $ 1 \le P \le 10^9 $ - $ 1 \le X \le Y \le 10^9 $ - $ 1 \le A_i \le 10^{18} $ - $ 1 \le C_i \le 10^9 $ - 全てのテストケースにおける $ N $ の総和は $ 2 \times 10^5 $ 以下 - 入力される値は全て整数