← 返回题目列表

AtCoder · utpc2022_g

G. K 翻转

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

配点 : 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