← 返回题目列表

Codeforces · 1941/F

F. 鲁道夫和不平衡

中文机器翻译题面 查看原题

Rudolf 准备了一组复杂度为 $$$a_1 < a_2 < a_3 < \dots < a_n$$$ 的 $$$n$$$ 问题。他对平衡性并不完全满意,因此他最多想添加一个问题来修复它。

为此,Rudolf 提出了 $$$m$$$ 问题模型和 $$$k$$$ 函数。第 $$$i$$$ 个模型的复杂度为 $$$d_i$$$,第 $$$j$$$ 个函数的复杂度为 $$$f_j$$$。为了创建一个问题,他选择值 $$$i$$$ 和 $$$j$$$ ($$$1 \le i \le m$$$, $$$1 \le j \le k$$$) 并通过将 $$$i$$$-th 模型与 $$$j$$$-th 函数相结合,他获得了一个复杂的新问题 $$$d_i + f_j$$$ (一个新元素被插入到数组中$$$a$$$)。

为了确定集合的不平衡性,Rudolf 按升序对问题的复杂性进行排序,并找到 $$$a_i - a_{i - 1}$$$ ($$$i > 1$$$) 的最大值。

鲁道夫通过添加最多一个问题(根据所描述的规则创建)可以实现的最小不平衡值是多少?

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le m, k \le 2 \cdot 10^5$$$)——分别是准备的问题数量、模型数量和函数数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, a_3, \dots a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^9$$$, $$$a_i < a_{i+1}$$$) — 准备问题的复杂性。

每个测试用例的第三行包含 $$$m$$$ 整数 $$$d_1, d_2, d_3, \dots d_m$$$ ($$$1 \le d_i \le 10^9$$$) - 模型的复杂性。

每个测试用例的第四行包含 $$$k$$$ 整数 $$$f_1, f_2, f_3, \dots f_k$$$ ($$$1 \le f_i \le 10^9$$$) — 函数的复杂性。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

保证所有测试用例的 $$$m$$$ 总和不超过 $$$2 \cdot 10^5$$$。

保证所有测试用例的 $$$k$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个数字——鲁道夫可以实现的最小不平衡。

示例

输入 #1

7
5 5 5
5 10 15 20 26
11 14 16 13 8
16 4 5 3 1
7 6 5
1 4 7 10 18 21 22
2 3 5 7 4 2
6 8 9 3 2
7 6 5
1 4 7 10 18 21 22
2 3 5 7 4 2
6 8 13 3 2
5 6 3
2 10 13 20 25
11 6 10 16 14 5
6 17 15
4 2 2
11 12 14 15
19 14
10 6
8 4 2
3 10 16 18 21 22 29 30
9 13 16 15
4 2
2 4 7
4 21
4 15 14 5
20 1 15 1 12 5 11

输出 #1

5
4
5
8
2
7
11