配点 : 100 点
問題文
在黑板上 N 整数 给出了 A_1, A_2, \ldots, A_N 被写下了。你可以选择进行以下操作 N - 1 次。 指定
- 黑板上写的数 2 次并删除。删除的数字 x 和 按字典顺序比较 y ,K - x - y 新写到黑板上。
N - 1 次操作结束后,黑板上只剩一个整数,这个整数可能的最大值是多少?
制約
- 所有输入均为整数
- 2 \le N \le 2 \times 10^5
- 1 \le K \le 10^9
- 1 \le A_i \le 10^9
入力
输入是按以下格式从标准输入给出的。
N K A_1 A_2 \ldots A_N
出力
答案 请打印除以 1 行输出。
入力例 1
4 3 1 2 3 4
出力例 1
7
例如,通过以下操作可以让 7 剩下。选择
- 1 和 按字典顺序比较 2 从黑板上删除,并把3 - 1 - 2 = 0 写到黑板上,由于不会有比
- 3 和 按字典顺序比较 4 从黑板上删除,并把3 - 3 - 4 = -4 写到黑板上,由于不会有比
- 0 和 按字典顺序比较 -4 从黑板上删除,并把3 - 0 - (-4) = 7 写到黑板上,由于不会有比
7 更大的数最后剩下,所以答案是 7 。 对于
入力例 2
4 7 1 2 3 4
出力例 2
5
例如,通过以下操作可以让 5 剩下。选择
- 1 和 按字典顺序比较 2 从黑板上删除,并把7 - 1 - 2 = 4 写到黑板上,由于不会有比
- 4 和 按字典顺序比较 4 从黑板上删除,并把7 - 4 - 4 = -1 写到黑板上,由于不会有比
- 3 和 按字典顺序比较 -1 从黑板上删除,并把7 - 3 - (-1) = 5 写到黑板上,由于不会有比
5 更大的数最后剩下,所以答案是 5 。 对于
入力例 3
10 3 1 4 1 5 9 2 6 5 3 5
出力例 3
32