| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (하단 참고) | 512 MB | 139 | 38 | 34 | 50.746% |
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)$ 값을 계산할 수 있다:
$A$, $B$, $D$가 주어졌을 때 $C(D)$값을 계산하는 문제는 너무 쉽기 때문에 Albert는 다음과 같은 새로운 놀이를 생각했다: $A$, $B$와 함께 임의의 정수 $K$가 주어졌을 때 $C(D) = K$ 가 되는 $D$가 존재하는지 판별하고, 존재한다면 그 중 가장 작은 $D$값을 찾아보자.
첫 줄에 테스트 케이스의 수 $T$가 주어진다.
각 테스트 케이스의 첫 줄에는 $N$과 $K$가 주어진다. 둘째 줄에는 배열 $A$의 정수 $N$개가 공백으로 구분되어 주어진다. 셋째 줄에는 배열 $B$의 정수 $N$개가 공백으로 구분되어 주어진다.
각 테스트 케이스의 정답을 각 줄에 출력한다. 만약 조건을 만족하는 $D$가 없다면 -1을 출력한다.
5 5 2 2 4 6 4 2 9 1 3 7 5 5 4 2 4 6 4 2 9 1 3 7 5 5 6 2 4 6 4 2 9 1 3 7 5 5 8 2 4 6 4 2 9 1 3 7 5 5 10 2 4 6 4 2 9 1 3 7 5
0 4 -1 6 10
예제 1-5: 본문에서 다룬 예제이며 $K$ 값만 바뀌는 경우를 보여준다.
1 9 18 1 2 3 4 5 4 3 2 1 5 4 3 2 1 2 3 4 5
2
예제 1: 총 18개의 $(i, j)$쌍을 제외하고는 모두 $Z(i, j) \gt 2$ 인데, $Z(1, 9)$ = $Z(2, 8)$ = $Z(3, 7)$ = $Z(4, 6)$ = $0$ 이고 $Z(1, 2)$ = $Z(1, 8)$ = $Z(2, 3)$ = $Z(2, 7)$ = $Z(2, 9)$ = $Z(3, 4)$ = $Z(3, 6)$ = $Z(3, 8)$ = $Z(4, 5)$ = $Z(4, 7)$ = $Z(5, 6)$ = $Z(6, 7)$ = $Z(7, 8)$ = $Z(8, 9)$ = $2$ 이므로 $C(2) = 18$ 이다.