B - Traffic Light 解説 /

実行時間制限: 4 sec / メモリ制限: 1024 MiB

配点 : 800 点

問題文

ある信号があります。この信号は常に赤になっていますが、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 個のテストケースが与えられるので、それぞれについて解いてください。

制約

  • 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 以下
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

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 の答えを出力せよ。

入力例 1

5
3 4 5 12
3 5 11
6 2 9
4 2 1 1
1 2 3 4
100 100 100 1
7 37 21 41
80 136 88 102 161 91 115
61 1 11 86 17 59 91
10 2763 2591 3369
2735 7773 36286 43737 9840 21707 19921 45759 44170 45287
3287 8050 3485 6845 3784 4565 3345 9297 2010 5550
15 408094769 859747485 886452311
1760053960 6327322912 490407029 1899495636 1174752626 84645660 6211206638 270040559 6098433044 4316510828 6601842919 5644655565 243073507 3150320792 4408022586
872391155 333542193 911310678 545186339 707811244 197915352 984885281 162966691 939525712 161385193 129092590 700676660 546046296 128723014 931663769

出力例 1

7
294
164
36403
6362927487

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 君は負の時刻にもボタンを押すことが出来ることに注意してください。

Score : 800 points

Problem Statement

There is a traffic signal. This signal is always red, but when PCT-kun pays P yen and presses a button, it becomes green for X seconds. However, he must follow the following rules:

  • The button can only be pressed at timings that can be expressed as time t for an integer t. (Negative integers can also be chosen as t.)
  • If the button is pressed at time t, it cannot be pressed until time t+Y. (It can be pressed at time t+Y.)

There are N people crossing this signal. The i-th person tries to cross this signal at time A_i + 0.5, and if the signal is green at time A_i + 0.5, they pay C_i yen to PCT-kun.

Find the maximum possible value of money received by PCT-kun minus the cost of pressing the button.

You are given T test cases; solve each of them.

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
  • The sum of N over all test cases is at most 2 \times 10^5.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each case is given in the following format:

N P X Y
A_1 A_2 \dots A_N
C_1 C_2 \dots C_N

Output

Output T lines. The i-th line (1 \le i \le T) should contain the answer for \mathrm{case}_i.

Sample Input 1

5
3 4 5 12
3 5 11
6 2 9
4 2 1 1
1 2 3 4
100 100 100 1
7 37 21 41
80 136 88 102 161 91 115
61 1 11 86 17 59 91
10 2763 2591 3369
2735 7773 36286 43737 9840 21707 19921 45759 44170 45287
3287 8050 3485 6845 3784 4565 3345 9297 2010 5550
15 408094769 859747485 886452311
1760053960 6327322912 490407029 1899495636 1174752626 84645660 6211206638 270040559 6098433044 4316510828 6601842919 5644655565 243073507 3150320792 4408022586
872391155 333542193 911310678 545186339 707811244 197915352 984885281 162966691 939525712 161385193 129092590 700676660 546046296 128723014 931663769

Sample Output 1

7
294
164
36403
6362927487

For the first test case, here is an example of PCT-kun's actions:

  • Pay 4 yen and press the button at time -1. This makes the signal green from time -1 to time 4.
  • Person 1 comes at time 3.5. Since the signal is green, they pay 6 yen to him.
  • Person 2 comes at time 5.5. Since the signal is red, nothing happens.
  • Pay 4 yen and press the button at time 11. This makes the signal green from time 11 to time 16.
  • Person 3 comes at time 11.5. Since the signal is green, they pay 9 yen to him.

In this case, the money received by him minus the cost of pressing the button is 7 yen, and it can be proved that 7 yen is the maximum value.

For the second test case, here is an example of his actions:

  • Pay 2 yen and press the button at time 1. This makes the signal green from time 1 to time 2.
  • Person 1 comes at time 1.5. Since the signal is green, they pay 100 yen to him.
  • Pay 2 yen and press the button at time 2. This makes the signal green from time 2 to time 3.
  • Person 2 comes at time 2.5. Since the signal is green, they pay 100 yen to him.
  • Pay 2 yen and press the button at time 3. This makes the signal green from time 3 to time 4.
  • Person 3 comes at time 3.5. Since the signal is green, they pay 100 yen to him.

In this case, the money received by him minus the cost of pressing the button is 294 yen, and it can be proved that 294 yen is the maximum value.

Note that he can press the button at negative times.