------Read problems statements in Mandarin chinese
, Russian and Vietnamese as well. ------

Professor GukiZ decided to distribute all of his candies to his $N$ students (numbered $1$ through $N$). Let's denote the number of candies GukiZ gave to the $i$-th student by $p_{i}$. As GukiZ has a lot of students, he does not remember all the exact numbers of candies he gave to the students. He only remembers the following properties of the sequence $p$:
The numbers of candies given to each of the first $K$ students ($p_{1}, p_{2}, \dots, p_{K}$) are known exactly.
All elements of the sequence $p$ are distinct.
The difference between the maximum and minimum element of the sequence $p$ does not exceed $x$.
The professor gave out the biggest possible total number of candies, i.e. $S = p_{1} + p_{2} + p_{3} + \ldots + p_{N}$ is maximum possible.

Normally, professors never lie, so the information provided by GukiZ is valid and there is at least one sequence that satisfies all conditions. GukiZ would like to know the total number of candies $S$ he had at the beginning. Can you help him find this number?

------ Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains three space-separated integers $N$, $K$ and $x$.
The second line contains $K$ space-separated integers $p_{1}, p_{2}, \dots, p_{K}$.

------ Output ------
For each test case, print a single line containing one integer — the number of candies GukiZ had.

------ Constraints ------
$1 ≤ T ≤ 50$
$1 ≤ N ≤ 10^{9}$
$1 ≤ K ≤ \mathrm{min}(N, 2 \cdot 10^{4})$
$0 ≤ x ≤ 10^{9}$
$1 ≤ p_{i} ≤ 10^{9}$ for each valid $i$
there is at least one valid distribution of candies to students

----- Sample Input 1 ------
2
4 3 4
2 1 5
2 2 9
3 6
----- Sample Output 1 ------
12
9
----- explanation 1 ------
Example case 1: There are four students. We know that the first student got $p_{1} = 2$ candies, the second student got $p_{2} = 1$ and the third got $p_{3} = 5$ candies; we don't know the number of candies given to the last student. The difference between the maximum and minimum number of candies given to students is already $5-1 = 4 = x$, so the fourth student could only have been given between $1$ and $5$ candies. It can't be $5$ either, so we maximize the number of candies if we give $4$ candies to the fourth student. In total, there are $2 + 1 + 5 + 4 = 12$ candies.

Example case 2: We know the number of candies given to each of the two students, so we know that GukiZ had $3 + 6 = 9$ candies.

见题面

见题面