E - Choose Two and Eat One Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

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

出力

答えを出力せよ。

入力例 1

4 10
4 2 3 2

出力例 1

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 点であり、これがあり得る最大値です。

入力例 2

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

出力例 2

1733

Score : 500 points

Problem Statement

A box contains N balls, each with an integer between 1 and M-1 written on it. For i = 1, 2, \ldots, N, the integer written on the i-th ball is A_i.

While the box has two or more balls remaining, Takahashi will repeat the following.

  • First, choose two balls arbitrarily.
  • Then, get a score equal to the remainder when x^y + y^x is divided by M, where x and y are the integers written on the two balls.
  • Finally, choose one of the two balls arbitrarily, eat it, and return the other to the box.

Print the maximum possible total score Takahashi will get.

Constraints

  • 2 \leq N \leq 500
  • 2 \leq M \leq 10^9
  • 1 \leq A_i \leq M-1
  • 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

4 10
4 2 3 2

Sample Output 1

20

Consider the following scenario. Below, X \bmod Y denotes the remainder when a non-negative integer X is divided by a positive integer Y.

  1. Take the first and third balls from the box to score (4^3 + 3^4) \bmod 10 = 5 points. Then, eat the first ball and return the third to the box. Now, the box has the second, third, and fourth balls.
  2. Take the third and fourth balls from the box to score (3^2 + 2^3) \bmod 10 = 7 points. Then, eat the third ball and return the fourth to the box. Now, the box has the second and fourth balls.
  3. Take the second and fourth balls from the box to score (2^2 + 2^2) \bmod 10 = 8 points. Then, eat the second ball and return the fourth to the box. Now, the box has just the fourth ball.

Here, Takahashi scores a total of 5 + 7 + 8 = 20 points, which is the maximum possible value.

Sample Input 2

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

Sample Output 2

1733