AT_abc282_e [ABC282E] Choose Two and Eat One

题目描述

一个盒子里有 $N$ 个球，每个球上写有一个介于 $1$ 和 $M-1$ 之间的整数。对于 $i=1,2,...,n$，第 $i$ 个球上写的整数是 $A_i$。

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

• 首先，任意选择两个球；
• 然后，得到一个分数，该分数等于 $(x^y+y^x) \bmod M$ ，其中 $x$ 和 $y$ 是两个球上写的整数，$x \bmod M$ 表示 $x$ 除以 $M$ 得到的余数；
• 最后，任意选择其中一个球，吃掉它，并将另一个球放回盒子中。

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

输入格式

输入通过标准输入从以下格式给出：

$N\ M$
$A_1\ A_2\ ...\ A_N$

输出格式

打印答案，即高桥能获得的最大总分。

输入输出样例 #1

输入 #1

4 10
4 2 3 2

输出 #1

20

输入输出样例 #2

输入 #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

说明/提示

数据规模与约定

对于 $100\%$ 的测试点数据，保证：

• $2 \le N \le 500$
• $2 \le M \le 10^9$
• $1 \le A_i \le M-1$
• 输入的所有数值均为整数。

样例 $1$ 解释

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