测试数据来自 wjszez/1990

[COCI2018-2019#1] Cipele

题目描述

在各种各样的项目上消耗经费之后，Nadan 决定为软件开发者提供高质量的鞋子。

Nadan 在地下室找到了 \(N\) 只左脚鞋和 \(M\) 只右脚鞋。因为它们的来源未知，因此鞋子的大小也不尽相同。

Nadan 想让你配对尽可能多的鞋子（即在所有鞋子配对完毕后不能继续配对）。每一对应当包含一只左脚鞋和一只右脚鞋。当穿上一双鞋时，应当使得鞋子的丑陋度最小化。一双鞋子的丑陋度定义为：所有配对的鞋子中，左脚和右脚大小之差的绝对值的最大值。

输入格式

第一行输入正整数 \(N,M\)，分别表示左脚鞋和右脚鞋的数量。

第二行输入 \(N\) 个整数 \(L_i\)，表示左脚鞋的大小。

第二行输入 \(M\) 个整数 \(R_i\)，表示右脚鞋的大小。

输出格式

输出所有配对方式中丑陋度的最小值。

样例 #1

样例输入 #1

2 3
2 3
1 2 3

样例输出 #1

0

样例 #2

样例输入 #2

4 3
2 39 41 45
39 42 46

样例输出 #2

1

样例 #3

样例输入 #3

5 5
7 6 1 2 10
9 11 6 3 12

样例输出 #3

4

提示

样例 2 解释

Nadan 的左脚鞋有 \(4\) 只，右脚鞋有 \(3\) 只，最多可以配成 \(3\) 对。一种配对方式为：**39-46**，41-42，45-39，第一双的两只鞋大小之差的绝对值最大，因而丑陋度为 \(7\)。

一种更好的配对方式为：39-39，41-42，45-46。该配对方式的丑陋度为 \(1\)，为所有配对方式中，丑陋度最小的。

数据规模与约定

对于 \(20\%\) 的数据，\(N=M\)。

对于另外 \(50\%\) 的数据，\(N,M \le 5000\)。

对于 \(100\%\) 的数据，\(1 \le N,M \le 10^5\)，\(1 \le L_i,R_i \le 10^9\)。

说明

本题分值按 COCI 原题设置，满分 \(90\)。

题目译自 COCI2018-2019 CONTEST #1 T3 Cipele。