CF1941F Rudolf and Imbalance

Rudolf 准备了一组 $n$ 个题目，其难度为 $a_1 < a_2 < a_3 < \dots < a_n$。他对这组题目的平衡性不是很满意，因此想通过最多添加一道题目来进行调整。 为此，Rudolf 准备了 $m$ 种题目模型和 $k$ 个函数。第 $i$ 个模型的难度为 $d_i$，第 $j$ 个函数的难度为 $f_j$。他可以选择一个模型和一个函数（$1 \le i \le m$，$1 \le j \le k$），将它们组合，得到一道新题目，其难度为 $d_i + f_j$（新题目的难度会插入到数组 $a$ 中）。 为了衡量题目的不平衡性，Rudolf 会将所有题目的难度升序排序，找到最大的 $a_i - a_{i-1}$（$i > 1$）。 请问，Rudolf 通过上述规则最多添加一道题目后，能获得的最小不平衡值是多少？

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含三个整数 $n$、$m$ 和 $k$（$2 \le n \le 10^5$，$1 \le m, k \le 2 \times 10^5$），分别表示已准备的题目数量、模型数量和函数数量。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 2 \times 10^9$，$a_i < a_{i+1}$），表示已准备题目的难度。 每个测试用例的第三行包含 $m$ 个整数 $d_1, d_2, \dots, d_m$（$1 \le d_i \le 10^9$），表示模型的难度。 每个测试用例的第四行包含 $k$ 个整数 $f_1, f_2, \dots, f_k$（$1 \le f_i \le 10^9$），表示函数的难度。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。 保证所有测试用例中 $m$ 的总和不超过 $2 \times 10^5$。 保证所有测试用例中 $k$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出一个整数，表示 Rudolf 通过最多添加一道题目后能获得的最小不平衡值。

由 ChatGPT 4.1 翻译