← 返回题目列表

AtCoder · yahoo_procon2017_final_b

B. 团队选择

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

配点 : 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