/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
高橋君は N 枚のカードを手札として持っています。 i = 1, 2, \ldots, N について、i 番目のカードには非負整数 A_i が書かれています。
高橋君は、まず手札から好きなカードを 1 枚選んで、テーブルの上に置きます。 その後、高橋君は好きな回数（ 0 回でも良い）だけ、下記の操作を繰り返します。
- 最後にテーブルの上に置いたカードに書かれた整数を X とする。手札に整数 X または整数 (X+1)\bmod M が書かれたカードがあれば、そのうち好きなものを 1 枚選んで、テーブルの上に置く。ここで、(X+1)\bmod M は (X+1) を M で割ったあまりを表す。
最終的に手札に残ったカードに書かれている整数の総和としてあり得る最小値を出力してください。
制約
- 1 \leq N \leq 2 \times 10^5
- 2 \leq M \leq 10^9
- 0 \leq A_i \lt M
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 \ldots A_N
出力
答えを出力せよ。
入力例 1
9 7 3 0 2 5 5 3 0 6 3
出力例 1
11
高橋君が、まず 4 番目のカード（書かれた整数は 5 ）をテーブルの上に置き、その後、以下の手順で操作を行う場合を考えます。
- 5 番目のカード（書かれた整数は 5 ）をテーブルの上に置く。
- 8 番目のカード（書かれた整数は 6 ）をテーブルの上に置く。
- 2 番目のカード（書かれた整数は 0 ）をテーブルの上に置く。
- 7 番目のカード（書かれた整数は 0 ）をテーブルの上に置く。
このとき、最終的に手札に残ったカードは、1, 3, 6, 9 枚目のカードであり、それらに書かれた整数の総和は 3 + 2 + 3 +3 = 11 です。 これが、最終的に手札に残ったカードに書かれている整数の総和としてあり得る最小値です。
入力例 2
1 10 4
出力例 2
0
入力例 3
20 20 18 16 15 9 8 8 17 1 3 17 11 9 12 11 7 3 2 14 3 12
出力例 3
99
Score : 400 points
Problem Statement
Takahashi has N cards in his hand. For i = 1, 2, \ldots, N, the i-th card has an non-negative integer A_i written on it.
First, Takahashi will freely choose a card from his hand and put it on a table. Then, he will repeat the following operation as many times as he wants (possibly zero).
- Let X be the integer written on the last card put on the table. If his hand contains cards with the integer X or the integer (X+1)\bmod M written on them, freely choose one of those cards and put it on the table. Here, (X+1)\bmod M denotes the remainder when (X+1) is divided by M.
Print the smallest possible sum of the integers written on the cards that end up remaining in his hand.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 2 \leq M \leq 10^9
- 0 \leq A_i \lt M
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 A_2 \ldots A_N
Output
Print the answer.
Sample Input 1
9 7 3 0 2 5 5 3 0 6 3
Sample Output 1
11
Assume that he first puts the fourth card (5 is written) on the table and then performs the following.
- Put the fifth card (5 is written) on the table.
- Put the eighth card (6 is written) on the table.
- Put the second card (0 is written) on the table.
- Put the seventh card (0 is written) on the table.
Then, the first, third, sixth, and ninth cards will end up remaining in his hand, and the sum of the integers on those cards is 3 + 2 + 3 +3 = 11. This is the minimum possible sum of the integers written on the cards that end up remaining in his hand.
Sample Input 2
1 10 4
Sample Output 2
0
Sample Input 3
20 20 18 16 15 9 8 8 17 1 3 17 11 9 12 11 7 3 2 14 3 12
Sample Output 3
99