AT_agc075_b.[AGC075B] Traffic Light

有一个交通信号灯。这个信号灯一直是红色，但当 PCT-kun 支付 $P$ 日元并按下按钮时，信号灯会变成绿色 $X$ 秒。然而，他必须遵循以下规则：

• 按钮只能在可以表示为整数 $t$ 时刻按下（$t$ 可以为负整数）。
• 如果在 $t$ 时刻按下按钮，则 $t+Y$ 之前都不能再次按下按钮（可以在 $t+Y$ 时再次按下）。

有 $N$ 个人需要通过该信号灯。第 $i$ 个人企图在 $A_i + 0.5$ 时刻通过信号灯，如果此时信号灯为绿色，他会向 PCT-kun 支付 $C_i$ 日元。

求 PCT-kun 所获得的最大收益（收到的总金额减去按下按钮所花费的金额）。

给定 $T$ 组测试数据，请你解决每组数据。

输入通过标准输入给出，格式如下：

$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

对于第一个测试点，PCT-kun 的操作如下：

• 支付 $4$ 日元，在时刻 $-1$ 按下按钮。此时信号灯在 $-1$ 到 $4$ 时刻为绿色。
• 第 $1$ 个人在 $3.5$ 时刻到来，信号灯为绿色，他会支付 $6$ 日元。
• 第 $2$ 个人在 $5.5$ 时刻到来，信号灯为红色，无支付。
• 支付 $4$ 日元，在时刻 $11$ 按下按钮。此时信号灯在 $11$ 到 $16$ 时刻为绿色。
• 第 $3$ 个人在 $11.5$ 时刻到来，信号灯为绿色，他会支付 $9$ 日元。

此时，收到的总金额减去支出为 $7$ 日元，且可以证明 $7$ 是最大值。

对于第二个测试点，PCT-kun 的操作如下：

• 支付 $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$ 日元，且可以证明这是最大值。

注意，也可以在负数时刻按下按钮。

数据范围

• $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$。
• 所有输入均为整数。

由 ChatGPT 5 翻译