← 返回题目列表

AtCoder · agc032_e

E. 模数配对

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

分数: 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.