[AGC032E] Modulo Pairing

题面翻译

令 $M$ 为一正整数。

给出 $2 N$ 个整数 $a_1, a_2, \ldots , a_{2N}$，满足 $0 \le a_i < M$。

你需要把这 $2 N$ 个整数分成 $N$ 对，每一对 $(x, y)$ 的权值为 $(x + y) \bmod M$。

令一种分配方案的权值为每一对的权值的最大值，请问权值最小的分配方案的权值为多少？

• $1 \le N \le {10}^5$，$1 \le M \le {10}^9$，$0 \le a_i < M$。

题目描述

$M$ を正整数とします。

$2\ N$ 個の整数 $a_1,\ a_2,\ \ldots,\ a_{2\ N}$ が与えられます。 ここで、各 $i$ について $0\ \leq\ a_i\ <\ M$ です。

$2\ N$ 個の整数を $N$ 組のペアに分けることを考えます。 このとき、各整数はちょうど $1$ つのペアに属さなければなりません。

ペア $(x,\ y)$ の 醜さ を $(x\ +\ y)\ \mod\ M$ と定義します。 $N$ 組のペアの醜さの最大値を $Z$ としたとき、$Z$ の最小値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $a_1$ $a_2$ $\cdots$ $a_{2N}$

输出格式

$N$ 組のペアの醜さの最大値を $Z$ としたとき、$Z$ の最小値を出力せよ。

样例 #1

样例输入 #1

3 10
0 2 3 4 5 9

样例输出 #1

5

样例 #2

样例输入 #2

2 10
1 9 1 9

样例输出 #2

0

提示

制約

• 入力はすべて整数である。
• $1\ \leq\ N\ \leq\ 10^5$
• $1\ \leq\ M\ \leq\ 10^9$
• $0\ \leq\ a_i\ <\ M$

Sample Explanation 1

例えば、$(0,\ 5),\ (2,\ 3),\ (4,\ 9)$ とペアを作ればよいです。 このとき、ペアの醜さはそれぞれ $5,\ 5,\ 3$ となります。

Sample Explanation 2

$(1,\ 9),\ (1,\ 9)$ とペアを作ればよいです。 このとき、ペアの醜さはともに $0$ です。