102824: [AtCoder]ABC282 E - Choose Two and Eat One

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

问题描述

一个盒子里有$N$个球，每个球上都写有一个1到$M-1$之间的整数。对于$i = 1, 2, \ldots, N$，第$i$个球上写的数是$A_i$。

当盒子中剩下两个或更多球时，高桥将重复以下操作。

• 首先，随意选择两个球。
• 然后，获得一个等于$x^y + y^x$除以$M$的余数的分数，其中$x$和$y$是两个球上写的数。
• 最后，随意选择其中一个球，吃掉它，将另一个球放回盒子中。

打印高桥可能获得的最大总分。

约束

• $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. 从盒子里取出第一个和第三个球，得分为$(4^3 + 3^4) \bmod 10 = 5$。然后，吃掉第一个球，将第三个球放回盒子。现在，盒子中有第二个、第三个和第四个球。
2. 从盒子里取出第三个和第四个球，得分为$(3^2 + 2^3) \bmod 10 = 7$。然后，吃掉第三个球，将第四个球放回盒子。现在，盒子中有第二个和第四个球。
3. 从盒子里取出第二个和第四个球，得分为$(2^2 + 2^2) \bmod 10 = 8$。然后，吃掉第二个球，将第四个球放回盒子。现在，盒子中只有一个第四个球。

在这里，高桥总共得分为$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