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

出力

答えを出力せよ。

9 7
3 0 2 5 5 3 0 6 3

11

高橋君が、まず $4$ 番目のカード（書かれた整数は $5$ ）をテーブルの上に置き、その後、以下の手順で操作を行う場合を考えます。

• $5$ 番目のカード（書かれた整数は $5$ ）をテーブルの上に置く。
• $8$ 番目のカード（書かれた整数は $6$ ）をテーブルの上に置く。
• $2$ 番目のカード（書かれた整数は $0$ ）をテーブルの上に置く。
• $7$ 番目のカード（書かれた整数は $0$ ）をテーブルの上に置く。

このとき、最終的に手札に残ったカードは、$1, 3, 6, 9$ 枚目のカードであり、それらに書かれた整数の総和は $3 + 2 + 3 +3 = 11$ です。 これが、最終的に手札に残ったカードに書かれている整数の総和としてあり得る最小値です。

1 10
4

0

20 20
18 16 15 9 8 8 17 1 3 17 11 9 12 11 7 3 2 14 3 12

99