{"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 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$.)\n*   If the button is pressed at time $t$, it cannot be pressed until time $t+Y$. (It can be pressed at time $t+Y$.)\n\nThere 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.\nFind the maximum possible value of money received by PCT-kun minus the cost of pressing the button.\nYou are given $T$ test cases; solve each of them.\n\n## Constraints\n\n*   $1 \\le T \\le 2 \\times 10^5$\n*   $1 \\le N \\le 2 \\times 10^5$\n*   $1 \\le P \\le 10^9$\n*   $1 \\le X \\le Y \\le 10^9$\n*   $1 \\le A_i \\le 10^{18}$\n*   $1 \\le C_i \\le 10^9$\n*   The sum of $N$ over all test cases is at most $2 \\times 10^5$.\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$T$\n$\\mathrm{case}_1$\n$\\mathrm{case}_2$\n$\\vdots$\n$\\mathrm{case}_T$\n\nEach case is given in the following format:\n\n$N$ $P$ $X$ $Y$\n$A_1$ $A_2$ $\\dots$ $A_N$\n$C_1$ $C_2$ $\\dots$ $C_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc075_b","tags":[],"sample_group":[["5\n3 4 5 12\n3 5 11\n6 2 9\n4 2 1 1\n1 2 3 4\n100 100 100 1\n7 37 21 41\n80 136 88 102 161 91 115\n61 1 11 86 17 59 91\n10 2763 2591 3369\n2735 7773 36286 43737 9840 21707 19921 45759 44170 45287\n3287 8050 3485 6845 3784 4565 3345 9297 2010 5550\n15 408094769 859747485 886452311\n1760053960 6327322912 490407029 1899495636 1174752626 84645660 6211206638 270040559 6098433044 4316510828 6601842919 5644655565 243073507 3150320792 4408022586\n872391155 333542193 911310678 545186339 707811244 197915352 984885281 162966691 939525712 161385193 129092590 700676660 546046296 128723014 931663769","7\n294\n164\n36403\n6362927487\n\nFor the first test case, here is an example of PCT-kun's actions:\n\n*   Pay $4$ yen and press the button at time $-1$. This makes the signal green from time $-1$ to time $4$.\n*   Person $1$ comes at time $3.5$. Since the signal is green, they pay $6$ yen to him.\n*   Person $2$ comes at time $5.5$. Since the signal is red, nothing happens.\n*   Pay $4$ yen and press the button at time $11$. This makes the signal green from time $11$ to time $16$.\n*   Person $3$ comes at time $11.5$. Since the signal is green, they pay $9$ yen to him.\n\nIn 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.\nFor the second test case, here is an example of his actions:\n\n*   Pay $2$ yen and press the button at time $1$. This makes the signal green from time $1$ to time $2$.\n*   Person $1$ comes at time $1.5$. Since the signal is green, they pay $100$ yen to him.\n*   Pay $2$ yen and press the button at time $2$. This makes the signal green from time $2$ to time $3$.\n*   Person $2$ comes at time $2.5$. Since the signal is green, they pay $100$ yen to him.\n*   Pay $2$ yen and press the button at time $3$. This makes the signal green from time $3$ to time $4$.\n*   Person $3$ comes at time $3.5$. Since the signal is green, they pay $100$ yen to him.\n\nIn 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.\nNote that he can press the button at negative times."]],"created_at":"2026-03-03 11:01:13"}}