← 返回题目列表

AtCoder · agc075_b

B. 交通灯

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

有交通信号灯。这个信号一直是红色的,但是当PCT-kun支付时 P 日元并按下按钮,它会变成绿色 X 秒。但是,他必须遵守以下规则:

  • 该按钮只能在可以用时间表示的时机按下 t 为整数 t。 (也可以选择负整数为 t.)
  • 如果在某个时间按下按钮 t,直到时间才可以按下 t+Y。 (可以随时按 t+Y.)

有 N 人们穿越这个信号灯。的 i- 第一个人在某个时间尝试跨越此信号 A_i + 0.5,如果信号当时为绿色 A_i + 0.5,他们支付 C_i 日元兑换PCT君。

求 PCT-kun 收到的金钱的最大可能价值减去按下按钮的成本。

你被给予 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

对于第一个测试用例,以下是 PCT-kun 操作的示例:

  • 支付 4 日元并按时间按钮 -1。这使得信号从时间变为绿色 -1 到时间 4.
  • 人 当他们的编程技能达到时, 1 准时到来 3.5。由于信号是绿色的,他们付费 6 日元给他。
  • 人 当他们的编程技能达到时, 2 准时到来 5.5。由于信号是红色的,所以什么也没有发生。
  • 支付 4 日元并按时间按钮 11。这使得信号从时间变为绿色 11 到时间 16.
  • 人 当他们的编程技能达到时, 3 准时到来 11.5。由于信号是绿色的,他们付费 9 日元给他。

这种情况下,他收到的钱减去按下按钮的成本就是 7 日元,并且可以证明 7 日元为最大值。

对于第二个测试用例,以下是他的操作示例:

  • 支付 2 日元并按时间按钮 1。这使得信号从时间变为绿色 1 到时间 2.
  • 人 当他们的编程技能达到时, 1 准时到来 1.5。由于信号是绿色的,他们付费 100 日元给他。
  • 支付 2 日元并按时间按钮 2。这使得信号从时间变为绿色 2 到时间 3.
  • 人 当他们的编程技能达到时, 2 准时到来 2.5。由于信号是绿色的,他们付费 100 日元给他。
  • 支付 2 日元并按时间按钮 3。这使得信号从时间变为绿色 3 到时间 4.
  • 人 当他们的编程技能达到时, 3 准时到来 3.5。由于信号是绿色的,他们付费 100 日元给他。

这种情况下,他收到的钱减去按下按钮的成本就是 294 日元,并且可以证明 294 日元为最大值。

请注意,他可以在负数时间按下按钮。