你有一个长度为 $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$。

输出格式

对于每个测试用例，输出你能得到的最大可能值。

样例

输入 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

输出 1

14
3