Maximize the Minimum

Time limit4sMemory limit2048 MB

Summary

Given two arrays with per-element removal costs, find the largest possible minimum gap |a_i - b_j| across the remaining elements when total removal cost is at most s.

Level: Hard8 of 10
Topics: Binary search, Dynamic programming, Sorting
Solved: No attempts yet

Problem

You have an array $a$ of length $n$ and an array $b$ of length $m$ . You can choose to remove some elements from the arrays. Removing element $a_i$ costs $c_i$ coins, and removing element $b_j$ costs $d_j$ coins. Importantly, there should be at least one element left in $a$ and at least one left in $b$ .

When you are done removing the elements, you compute the following value:

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

You want to maximize this value. What is the maximum value you can get if you can spend at most $s$ coins in total?

Input

The first line contains an integer $t$ ( $1 \le t \le 2 \cdot 10^5$ ), the number of test cases. The test cases follow.

The first line of each test case contains integers $n$ ( $1 \le n \le 2 \cdot 10^5$ ), $m$ ( $1 \le m \le 2 \cdot 10^5$ ) and $s$ ( $0 \le s \le 10^{18}$ ). The next four lines contain integer arrays $a$ , $b$ , $c$ , $d$ , in this order ( $-10^9 \le a_i, b_j \le 10^9$ ; $1 \le c_i, d_j \le 10^{12}$ ). The arrays $a$ and $c$ have length $n$ . The arrays $b$ and $d$ have length $m$ .

The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ . The sum of $m$ over all test cases does not exceed $2 \cdot 10^5$ .

Output

For each test case, print the maximum possible value you can get.

Examples1

Example 1

Input

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

Expected output

14
3