D. Fever Dash
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

小 F 很喜欢玩《Fever Dash》这款音乐游戏。

一个关卡总共有 $$$n$$$ 枚音符，第 $$$i$$$ 枚音符有落下时刻 $$$t_i$$$、分数 $$$p_i$$$、Fever 值 $$$f_i$$$ 三个属性。

游戏的 Fever 机制如下：

  • 击打音符会累加其 Fever 值到 Fever 槽中，槽的上限为 $$$L$$$。一旦在某个时刻，Fever 槽的值达到 $$$L$$$，从下一个时刻开始的每个时刻都可以选择开启 Fever。
  • 开启 Fever 后，Fever 槽被清空，并进入持续 $$$k$$$ 个时刻的 Fever 状态。也就是说，如果在 $$$i$$$ 时刻开启 Fever 状态，则 $$$[i, i+k-1]$$$ 时刻都将处在 Fever 状态中。在该状态下，所有击打的音符分数翻倍，但无法获得 Fever 值。Fever 状态结束后才能重新开始积累。

具体来讲，每一时刻内，以下事件依次发生：

  • 如果 Fever 值达到了上限 $$$L$$$，小 F 可以选择是否开启 Fever 状态。开启 Fever 后，Fever 槽被清空。
  • 如果处在 Fever 状态中，并且当前时刻 $$$x$$$ 与开启 Fever 的时刻 $$$y$$$ 满足 $$$x - y \geq k$$$，则 Fever 状态结束。
  • 如果该时刻有音符落下，小 F 将会击打该音符：记这枚音符的编号为 $$$i$$$，若处于 Fever 状态，获得 $$$2 \times p_i$$$ 分，不累加 Fever 值；否则，获得 $$$p_i$$$ 分，并将 $$$f_i$$$ 累加到 Fever 槽。

游戏开始时不在 Fever 状态中，且 Fever 槽为 $$$0$$$。Fever 可以重复开启任意次，开启后无法手动关闭。注意在最后一个音符落下后 Fever 状态可以还没有结束。

给出 $$$n$$$ 个音符落下的时刻 $$$t_i$$$，分数 $$$p_i$$$ 和 Fever 值 $$$f_i$$$，小 F 想知道，如果他以最优方案开启 Fever 他能够获得多少分，你能帮帮他吗？

（题意与任何现实游戏的机制无关）

Input

第一行包含 $$$1$$$ 个整数 $$$T$$$（$$$1 \le T \le 1000$$$），表示数据组数。

每组数据的第一行为 $$$n$$$，$$$L$$$，$$$k$$$（$$$1 \le n \le 5 \times 10^5$$$，$$$1 \le L, k \le 10^9$$$）三个整数，分别是音符个数、Fever 槽上限、 Fever 持续时长。

下一行包含 $$$n$$$ 个整数 $$$t_i$$$（$$$1 \leq t_i \leq 10^9$$$），代表第 $$$i$$$ 个音符落下的时刻。

下一行包含 $$$n$$$ 个整数 $$$p_i$$$（$$$1 \leq p_i \leq 10^9$$$），代表击打第 $$$i$$$ 个音符获得的分数。

下一行包含 $$$n$$$ 个整数 $$$f_i$$$（$$$1 \leq f_i \leq 10^9$$$），代表击打第 $$$i$$$ 个音符累积的 Fever 值。

数据保证：

  • 多组数据的 $$$n$$$ 之和不超过 $$$5 \times 10^5$$$。
  • $$$t_i$$$ 单调递增，即对于任何 $$$1 \le i \lt n$$$, $$$t_i \lt t_{i+1}$$$。
Output

对于每组数据输出一个整数，表示获得的最大分值。

Example
Input
4
3 5 5
1 2 7
4 4 4
5 10 7
7 3 2
1 2 3 4 5 6 7
2 5 4 1 1 9 9
3 2 2 2 2 1 1
8 2 5
2 4 5 6 7 8 9 10
6 4 8 3 1 2 7 6
6 2 9 4 8 5 5 4
7 1 6
1 2 3 5 6 8 10
9 5 9 7 3 3 10
6 10 8 9 2 3 3
Output
16
58
66
80
Note

（方便起见，以下假设时刻的单位是秒）

对于第一组样例，在第 $$$1$$$ 秒获得 $$$4$$$ 分并获得 $$$5$$$ Fever 值，达到 Fever 上限；在第 $$$2$$$ 秒开启 Fever，获得 $$$8$$$ 分，不获得 Fever 值；在第 $$$7$$$ 秒时 Fever 已经结束，获得 $$$4$$$ 分和 $$$7$$$ Fever 值，共计 $$$16$$$ 分。

对于第二组样例，在第 $$$[2, 3]$$$ 秒和第 $$$[6, 7]$$$ 秒处于 Fever 状态最优。