[R7D]最小极差 - 代码源竞赛平台

时空限制

1S/512M

题目描述

给定一个长度为 $n$ 的整数数组 $A$ 和一个长度为 $m$ 的整数数组 $B$。

对于 $1\leq i\leq n$ 的每个 $i$，分别在 $1\leq j\leq m$ 中选择 $j$，构造长度为 $n$ 的整数数组 $C_i=A_i+B_j$。

定义 $C$ 的极差为 $\max\{C_i\}-\min\{C_i\}$，求 $C$ 的极差的最小值。

格式

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示数组 $A$ 的长度和数组 $B$ 的长度。

第二行包含 $n$ 个整数 $A_i$。

第三行包含 $m$ 个整数 $B_i$。

输出格式

输出一个整数表示 $\max\{C_i\}-\min\{C_i\}$ 的最小值。

样例

样例输入 #1

5 3
1 3 4 5 1
4 3 7

样例输出 #1

1

样例解释 #1

当 $C=\{8,7,8,8,8\}$ 时极差最小，其中 $C_1=A_1+B_3=8$，$C_2=A_2+B_1=7$，$C_3=A_3+B_1=8$，$C_4=A_4+B_2=8$，$C_5=A_5+B_3=8$。

数据规模

对于 $40\%$ 的数据，$n\leq 500$。

另有 $20\%$ 的数据，$A_i,B_i\leq 1000$。

对于 $100\%$ 的数据，$1\leq n\leq 3\times 10^5$，$1\leq m\leq 10$，$1\leq A_i,B_i\leq 10^{18}$。