当前没有测试数据。

E - 选择两个来吃一个

得分：$500$ 分

问题描述

一个盒子里有 $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$

输出

输出结果。

4 10
4 2 3 2

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$ 分，这是可能的最大值。

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

1733