G - K flipping
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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