配点 : $500$ 点

問題文

箱の中に $N$ 個のボールが入っており、各ボールには $1$ 以上 $M-1$ 以下の整数が書かれています。 $i = 1, 2, \ldots, N$ について、$i$ 番目のボールに書かれた整数は $A_i$ です。

高橋君は、箱の中に $2$ 個以上のボールが残っている限り、下記の行動を繰り返します。

• まず、箱の中から $2$ つのボールを任意に選んで取り出す。
• 次に、取り出した $2$ つのボールに書かれた整数をそれぞれ $x, y$ とおき、$x^y + y^x$ を $M$ で割ったあまりに等しい得点を獲得する。
• その後、取り出した $2$ つのボールのうち、任意に選んだ一方を食べ、もう一方を箱の中に戻す。

高橋君が獲得する合計得点としてあり得る最大値を出力してください。

制約

• $2 \leq N \leq 500$
• $2 \leq M \leq 10^9$
• $1 \leq A_i \leq M-1$
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$

$A_1$ $A_2$ $\ldots$ $A_N$

出力

答えを出力せよ。

4 10
4 2 3 2

20

高橋君が下記の通りに行動する場合を考えます。以下、$X \bmod Y$ で 非負整数 $X$ を正整数 $Y$ で割ったあまりを表します。

1. 箱の中から $1$ 番目のボールと $3$ 番目のボールを取り出し、$(4^3 + 3^4) \bmod 10 = 5$ 点を獲得します。その後、$1$ 番目のボールを食べ、$3$ 番目のボールを箱の中に戻します。その結果、箱の中には $2, 3, 4$ 番目のボールが残ります。
2. 箱の中から $3$ 番目のボールと $4$ 番目のボールを取り出し、$(3^2 + 2^3) \bmod 10 = 7$ 点を獲得します。その後、$3$ 番目のボールを食べ、$4$ 番目のボールを箱の中に戻します。その結果、箱の中には $2, 4$ 番目のボールが残ります。
3. 箱の中から $2$ 番目のボールと $4$ 番目のボールを取り出し、$(2^2 + 2^2) \bmod 10 = 8$ 点を獲得します。その後、$2$ 番目のボールを食べ、$4$ 番目のボールを箱の中に戻します。その結果、箱の中には $4$ 番目のボールのみが残ります。

このとき、高橋君が獲得する合計得点は $5 + 7 + 8 = 20$ 点であり、これがあり得る最大値です。

20 100
29 31 68 20 83 66 23 84 69 96 41 61 83 37 52 71 18 55 40 8

1733