가장 작은 값을 최대로 만들기

시간 제한4초메모리 제한2048 MB

요약

두 배열의 원소마다 삭제 비용이 주어졌을 때, 총 비용을 s 이하로 써서 남은 a의 원소와 b의 원소 사이 차이의 최솟값을 가장 크게 만드는 값을 구합니다.

난이도: 어려움10점 중 8점
유형: 이분 탐색, 동적 계획법, 정렬
정답자: 아직 제출이 없습니다

문제

길이 $n$ 의 배열 $a$ 와 길이 $m$ 의 배열 $b$ 가 있다. 배열에서 일부 원소를 제거할 수 있다. 원소 $a_i$ 를 제거하는 데 $c_i$ 코인이 들고, 원소 $b_j$ 를 제거하는 데 $d_j$ 코인이 든다. 단, $a$ 에는 원소가 적어도 하나 남아 있어야 하고, $b$ 에도 원소가 적어도 하나 남아 있어야 한다.

원소 제거를 마치면 다음 값을 계산한다.

$\min_{\substack{1 \le i \le n \\ 1 \le j \le m}} |a_i - b_j|$

이 값을 최대로 만들고 싶다. 전체적으로 최대 $s$ 코인까지 쓸 수 있을 때, 얻을 수 있는 값의 최댓값은 얼마인가?

입력

첫 줄에 테스트 케이스의 수 $t$ ( $1 \le t \le 2 \cdot 10^5$ )가 주어진다. 이후 테스트 케이스가 이어진다.

각 테스트 케이스의 첫 줄에는 정수 $n$ ( $1 \le n \le 2 \cdot 10^5$ ), $m$ ( $1 \le m \le 2 \cdot 10^5$ ), $s$ ( $0 \le s \le 10^{18}$ )가 주어진다. 다음 네 줄에는 차례대로 정수 배열 $a$ , $b$ , $c$ , $d$ 가 주어진다 ( $-10^9 \le a_i, b_j \le 10^9$ ; $1 \le c_i, d_j \le 10^{12}$ ). 배열 $a$ 와 $c$ 의 길이는 $n$ 이고, 배열 $b$ 와 $d$ 의 길이는 $m$ 이다.

모든 테스트 케이스에 대해 $n$ 의 합은 $2 \cdot 10^5$ 를 넘지 않는다. $m$ 의 합도 $2 \cdot 10^5$ 를 넘지 않는다.

출력

각 테스트 케이스마다, 전체적으로 최대 $s$ 코인을 사용해 얻을 수 있는 값의 최댓값을 출력한다.

예제1

예제 1

입력

2
1 4 10
15
1 6 9 13
8
3 1 2 4
5 4 4
-1 5 3 2 -4
-7 8 6 2
2 3 1 1 2
3 1 1 1

예상 출력

14
3