특별한 정수쌍 세기

Albert는 정수 배열을 이용하여 특별한 정수쌍 세는 놀이를 즐겨한다. 우선 임의로 길이가 $N$인 두 정수 배열 $A$, $B$를 고른 후 아래와 같이 2차원 배열 $X$, $Y$, $Z$ 를 정의한다: $1 \le i \lt j \le N$ 인 정수 $i, j$에 대하여: $X(i, j) = A\_i - A\_j$ 이고 $Y(i, j) = B\_i - B\_j$ 이며 $Z(i, j) = | X(i, j) - Y(i, j) |$ 이다 ($Z(i, j)$는 절댓값이다). 마지막으로 $Z$를 이용하여 $C$를 정의한다: $C(D) = | \\{(i, j) : Z(i, j) \le D \\} |$. 즉, $C(D)$는 $Z(i, j)$ 가 $D$ 이하인 "특별한 정수쌍" $(i, j)$의 개수를 나타낸다 (물론 $1 \le i \lt j \le N$ 인 경우만 고려한다).

예를 들어 $N = 5$, $A = \[2, 4, 6, 4, 2]$, $B = \[9, 1, 3, 7, 5]$ 라 하자. 아래 그림은 순서대로 $X$, $Y$, $Z$ 2차원 배열의 값을 나타낸다. 행은 i인덱스, 열은 j인덱스를 나타낸다.

위 정보를 활용하면 다양한 $D$ 값에 대하여 $C(D)$ 값을 계산할 수 있다:

• $D$ = 0: $Z(2, 3) = Z(4, 5) = 0$ 이므로 $C(0) = 2$ 가 된다.
• $D$ = 4: $Z(i, j) = 0$ 인 경우가 두 쌍, $Z(i, j) = 4$인 경우가 두 쌍 있으므로 $C(4) = 4$가 된다.
• $D$ = 6: 이 경우 $Z(i, j) = 6$ 인 $(i, j)$ 쌍이 4개이므로, 앞서 언급한 네 쌍을 포함하여 $C(6) = 8$ 이 된다.
• $D$ = 10: 이 경우 모든 쌍을 포함하므로 $C(10) = 10$ 이 된다.
• $D$ = 20: 이 경우도 위와 마찬가지로 $C(20) = 10$이다.

$A$, $B$, $D$가 주어졌을 때 $C(D)$값을 계산하는 문제는 너무 쉽기 때문에 Albert는 다음과 같은 새로운 놀이를 생각했다: $A$, $B$와 함께 임의의 정수 $K$가 주어졌을 때 $C(D) = K$ 가 되는 $D$가 존재하는지 판별하고, 존재한다면 그 중 가장 작은 $D$값을 찾아보자.

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 $N$과 $K$가 주어진다. 둘째 줄에는 배열 $A$의 정수 $N$개가 공백으로 구분되어 주어진다. 셋째 줄에는 배열 $B$의 정수 $N$개가 공백으로 구분되어 주어진다.

각 테스트 케이스의 정답을 각 줄에 출력한다. 만약 조건을 만족하는 $D$가 없다면 -1을 출력한다.

• $1 \le T \le 5$
• $2 \le N \le 50000$
• $0 \le K \le N \times (N-1) / 2$
• $1 \le i \le N$ 인 $i$ 에 대하여: $0 \le A\[i], B\[i] \le 10^5$