Description

小 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 他能够获得多少分，你能帮帮他吗？

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

Format

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 < n$, $t_i < t_{i+1}$。

Output

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

Samples

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

16
58
66
80

Note

Note

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

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

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