Problem Description

ShwStone is playing a game called A Dance Of Ice And Fire (ADOIAF). It is a one-button rhythm game. ShwStone needs to press the key at the correct time. However, ShwStone is not very good, and often loses points because the timing is off. ShwStone wants to know: if all judgments could be matched in the way he wants, what is the maximum score he can get.

Formally, ADOIAF has $n$ judgment points $t_{a_1}, t_{a_2}, \cdots, t_{a_n}$. ShwStone presses the key $m$ times, and the press time sequence is $t_{b_1}, t_{b_2}, \cdots, t_{b_m}$. ADOIAF has a built-in judgment parameter $k$. If we choose to match the $j$-th key press with the $i$-th judgment point, the score gained is $\max(k^2 - (t_{a_i} - t_{b_j})^2, 0)$.

Note that in the final plan, each key press can satisfy at most one judgment point, and each judgment point can be satisfied at most once. There is no ordering requirement between matched key presses and judgment points.

You need to output the maximum total score.

Input Format

This problem contains multiple test cases. The first line contains a positive integer $T$ ($1 \le T \le 10^4$), representing the number of test cases.

Next are $T$ test cases.

For each test case, the first line contains three positive integers $n$, $m$, and $k$ ($1 \le n, m \le 10^5$, $1 \le k \le 50$), separated by spaces, representing the number of judgment points, the number of key presses, and the judgment parameter.

The next line contains $n$ positive integers $t_{a_1}, t_{a_2}, \cdots, t_{a_n}$ ($1 \le t_{a_i} \le 10^6$), separated by spaces, representing the time sequence of the judgment points. It is guaranteed that all $t_{a_i}$ are distinct. The input is not guaranteed to be sorted.

The next line contains $m$ positive integers $t_{b_1}, t_{b_2}, \cdots, t_{b_m}$ ($1 \le t_{b_j} \le 10^6$), separated by spaces, representing the time sequence of key presses. It is guaranteed that all $t_{b_j}$ are distinct. The input is not guaranteed to be sorted.

It is guaranteed that across all test cases, the sum of $n$ does not exceed $10^5$, and the sum of $m$ does not exceed $10^5$.

Output Format

For each test case, output one line containing a non-negative integer, representing the maximum score ShwStone can obtain under an optimal matching.

2
7 7 3
5 4 14 8 1 17 6
6 13 3 12 15 14 10
8 8 4
9 6 14 11 12 5 2 13
14 7 15 5 20 12 11 9

36
109

Hint

Translated by ChatGPT 5