Traffic Light

AtCoder

IDagc075_b

Time4000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

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

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.

API Response (JSON)

{
  "problem": {
    "name": "Traffic Light",
    "description": {
      "content": "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",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc075_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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:\n\n*   The button...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments