Counting Special Integer Pairs

Albert enjoys a game of counting special integer pairs using integer arrays. First he chooses two integer arrays $A$ and $B$ of length $N$ arbitrarily. Then for each pair of integers $1 \le i \lt j \le N$, he defines

$X(i, j) = A_i - A_j$, $Y(i, j) = B_i - B_j$, $Z(i, j) = |X(i, j) - Y(i, j)|$

Using $Z$, he defines $C(D) = |\{(i, j) : Z(i, j) \le D\}|$. In other words, $C(D)$ is the number of special pairs $(i, j)$ whose $Z(i, j)$ is at most $D$. Only pairs with $1 \le i \lt j \le N$ are considered.

Computing $C(D)$ from given $A$, $B$, and $D$ is easy, so Albert came up with a new game. Given $A$, $B$, and an integer $K$, determine whether some $D$ satisfies $C(D) = K$. If one exists, find the smallest such $D$.

The first line contains the number of test cases $T$. The first line of each test case contains $N$ and $K$. The second line contains the $N$ integers of array $A$, separated by spaces. The third line contains the $N$ integers of array $B$, separated by spaces.

For each test case, print the answer on its own line. If no $D$ satisfies the condition, print -1.

• $1 \le T \le 5$
• $2 \le N \le 50000$
• $0 \le K \le N \times (N-1) / 2$
• For all $i$ with $1 \le i \le N$: $0 \le A_i, B_i \le 10^5$