分数: 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
输出
打印答案。
示例输入 1
4 10 4 2 3 2
示例输出 1
20
考虑以下场景。下面, X \bmod Y 表示非负整数时的余数 X 除以正整数 Y.
- 从盒子里取出第一个和第三个球即可得分 (4^3 + 3^4) \bmod 10 = 5 点。然后,吃掉第一个球并将第三个球放回盒子里。现在,盒子里有第二个、第三个和第四个球。
- 从盒子里取出第三个和第四个球即可得分 (3^2 + 2^3) \bmod 10 = 7 点。然后,吃掉第三个球,并将第四个球放回盒子里。现在,盒子里有第二个和第四个球。
- 从盒子里取出第二个和第四个球即可得分 (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