I. Link into the Vrains
time limit per test
2 seconds
memory limit per test
128 megabytes
input
standard input
output
standard output

Da7doo7 is watching TV after getting laid off today.

Yusaku and Ignister are dueling in a Yugi-oh game in Vrains (the virtual city), where Yusaku is fighting for people, whereas Ignister is fighting for the future of AI.

Yusaku has $$$n$$$ link monsters on the field, and each of them has a location $$$x_i$$$ and power $$$p_i$$$ (possibly negative).

It is a crucial game, and both Yusaku and Ignister are doing their best to win. Now, it is Yusaku's turn where he wants to inflict as much damage as possible to Ignister to win the duel, where the damage is equal to the sum of the power of all monsters on the field.

However, Ignister activated the trap A.I.Q, this trap forces Yusaku to control at most $$$K$$$ monsters.

Link monsters are powerful monsters, they depend on their locations to make links between each other. Two monsters $$$a$$$ and $$$b$$$ are called linked if at least one of the following is satisfied:

  • The distance between $$$a$$$ and $$$b$$$ is strictly less than $$$D$$$.
  • If $$$a$$$ is linked to $$$c$$$ and $$$b$$$ is linked to $$$c$$$, then $$$a$$$ and $$$b$$$ are linked.

Monsters that are linked are treated as one monster. For example: if Yusaku has $$$4$$$ monsters, $$$a$$$, $$$b$$$, and $$$c$$$ that are linked, and a monster $$$d$$$ which is not linked to any other monster, the $$$4$$$ monsters are treated as $$$2$$$, not $$$4$$$.

Yusaku wants to destroy some of his monsters (possibly none or all of them) such that the number of remaining monsters on the field is at most $$$K$$$. Help Yusaku find the maximum damage he can inflict to Ignister.

Input

The first line of the input contains an integer $$$T$$$ ($$$1 \le T \le 10^5$$$) denoting the number of test cases.

The first line of each test case contains three integers $$$n$$$, $$$K$$$, and $$$D$$$ ($$$1 \le K \le n \le 10^5$$$, $$$1 \le D \le 10^9$$$) — the number of monsters, the maximum number allowed for controlling monsters, and the linking distance.

The second line of each test case contains $$$n$$$ integers $$$x_1, \ldots, x_n$$$ ($$$1 \le x_i \le 10^9$$$) — the location of monsters. It is guaranteed that $$$x$$$ is strictly increasing.

The last line of each test case contains $$$n$$$ integers $$$p_1, \ldots, p_n$$$ ($$$-10^5 \le p_i \le 10^5$$$) — the power of monsters.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, output the answer in a single line.

Example
Input
5
3 1 2
1 2 3
5 -2 5
3 2 2
1 2 3
5 -2 5
3 1 1
1 2 3
4 3 5
2 2 10
4 7
-7 -4
4 1 8
2 4 6 8
4 -10 -10 4
Output
8
10
5
0
8