AT_agc075_b [AGC075B] Traffic Light

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.

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 $ T $ lines. The $ i $ -th line $ (1 \le i \le T) $ should contain the answer for $ \mathrm{case}_i $ .

### Sample Explanation 1 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. ### 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.