Copou Grand Prix

Breaking news! Contestant Andu from Iași has announced that he will not attend the IIOT finals because the Copou Grand Prix will take place at the same time as the contest.

The Grand Prix consists of $N$ races in which $M$ drivers compete, two of whom are Alice and Bob. We know that Alice finished the races in positions $A_1, A_2, \ldots, A_N$, and Bob in positions $B_1, B_2, \ldots, B_N$.

Task

Because defeat is inevitable, Andu wants to assign the number of points $p_i$ awarded for each finishing position $i$ ($1 \leq i \leq M$) in such a way that the following conditions are met:

• $W = p_1 > p_2 > \ldots > p_M = 0$, where $W$ is a given positive integer.
• The value $D = \displaystyle \sum_{i=1}^{N} p_{A_i} - \sum_{i=1}^{N} p_{B_i}$ is maximized.

Once assigned, the points are the same for all $N$ races. Your task is to find the maximum possible value of $D$.

Input data

The first line of the input contains an integer $T$, representing the number of test cases. Each test case is described as follows:

• The first line contains three space-separated integers, $N$, $M$, and $W$, where $N$ is the number of races, $M$ is the number of drivers, and $W$ is the maximum number of points awarded for finishing in first place.
• The second line contains $N$ space-separated integers, $A_1, A_2, \ldots, A_N$, representing the Alices's finishing positions in each race.
• The third line contains $N$ space-separated integers, $B_1, B_2, \ldots, B_N$, representing the Bob's finishing positions in each race.

Output data

For each test case, you must output the maximum value achievable for $D$ on a separate line.

Constraints and clarifications

• $1 \leq T \leq 30 \ 000$
• $1 \leq N \leq 100 \ 000$
• $1 \leq M \leq 10^9$
• $M - 1 \leq W \leq 10^9$
• The sum of $N$ over all test cases will not exceed $300 \ 000$.
• $1 \leq A_i, B_i \leq M$
• $A_i \neq B_i$, for every $1 \leq i \leq N$

Example

stdin

6
6 5 5
1 1 3 3 3 5
1 2 2 3 4 5
8 12 15
1 1 2 2 3 3 6 11
1 2 2 3 5 5 7 9
8 12 15
1 2 2 3 5 5 7 9
1 1 2 2 3 3 6 11
4 8 10
5 6 7 8
1 2 3 4
6 6 5
1 2 3 4 5 6
1 2 3 4 5 6
10 6 6
2 3 3 3 4 4 6 6 6 6
2 2 2 3 3 4 4 4 5 6

stdout

2
13
-1
-19
0
-8

Explanation

In the first test case, the optimal number of points awarded for each position (with regard to maximizing $D$) is $[5, 3, 2, 1, 0]$.

For this point distribution, $D = (p_1+p_1+p_3+p_3+p_3+p_5) - (p_1+p_2+p_2+p_3+p_4+p_5)=(5+5+2+2+2+0)-(5+3+3+2+1+0)=16-14=2$.

In the second test case, an optimal point distribution is $[15, 14, 13, 10, 7, 6, 5, 4, 3, 2, 1, 0]$.