分数: 1200 点
问题陈述
让 M 是正整数。
你被给予 2 N 整数 a_1, a_2, \ldots, a_{2 N},其中 0 \leq a_i < M 对于每个 i.
考虑划分 2 N 整数到 N 对。 这里,每个整数必须恰好属于一对。
我们定义 丑陋 一对 (x, y) as (x + y) \mod M。 让 Z 最大的丑了 N 对。找到最小可能值 Z.
约束
- 输入中的所有值都是整数。
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^9
- 0 \leq a_i < M
输入
输入由标准输入按以下格式给出:
N M
a_1 a_2 \cdots a_{2N}
输出
打印以下的最小可能值 Z,其中 Z 最大的丑 N 对。
示例输入 1
3 10 0 2 3 4 5 9
示例输出 1
5
一种解决方案是结对 (0, 5), (2, 3) 和 (4, 9),丑陋 5, 5 和 3。
示例输入 2
2 10 1 9 1 9
示例输出 2
0
对 (1, 9) 和 (1, 9) 应成型,丑陋兼备 0.