Score : 1200 points
Let M be a positive integer.
You are given 2 N integers a_1, a_2, \ldots, a_{2 N}, where 0 \leq a_i < M for each i.
Consider dividing the 2 N integers into N pairs. Here, each integer must belong to exactly one pair.
We define the ugliness of a pair (x, y) as (x + y) \mod M. Let Z be the largest ugliness of the N pairs. Find the minimum possible value of Z.
Input is given from Standard Input in the following format:
N M a_1 a_2 \cdots a_{2N}
Print the minimum possible value of Z, where Z is the largest ugliness of the N pairs.
3 10 0 2 3 4 5 9
5
One solution is to form pairs (0, 5), (2, 3) and (4, 9), with ugliness 5, 5 and 3, respectively.
2 10 1 9 1 9
0
Pairs (1, 9) and (1, 9) should be formed, with ugliness both 0.