配点 : 600 点
問題文
在 ACoder,我们打算举办高桥队和青木队之间的团队编程比赛. 2 高桥队的参赛候选者有 N 人,高桥队的 i 名候选者的能力用 A_i 表示. 此外,青木队的参赛候选者有 M 人,青木队的 i 名候选者的能力用 B_i 用
表示. 在举办比赛之前,决定从高桥队和青木队各选 K 人参赛. 参赛者会从各自团队的候选者中选出. 此时,选择K 人参赛者时,团队间的实力差定义如下.
- 高桥队参赛者中 i 第几名能力值较高者的能力 X_i,在团队青木的参与者中 i 第几名能力值较高者的能力 Y_i 。
- 此时,团队之间的实力差是,max (|X_1 - Y_1|, |X_2 - Y_2|, ..., |X_K - Y_K| ) 。
请求出在确定各团队的参与者时,团队之间实力差的最小值。
制約
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 1 \leq K \leq min (N, M)
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
- A_i, B_i 是一个整数
入力
输入是按以下格式从标准输入给出的。
N M K A_1 A_2 ... A_N B_1 B_2 ... B_M
出力
输出团队之间实力差的最小值。
入力例 1
3 4 2 2 11 16 4 7 9 10
出力例 1
2
从团队高桥中 1, 2 第几位候选人,从团队青木中 1, 3 第几位候选人,作为参与者来选择比较好。 此时,团队高桥的参与者实力按从大到小的顺序 11, 2,团队青木的参与者实力按从大到小的顺序 9, 4 变为。
入力例 2
6 5 3 15 7 14 3 14 11 20 18 15 18 17
出力例 2
3