选两个吃一个

题目描述

一个盒子中有 $N$ 个球,每个球上写着一个介于 $1$ 和 $M-1$ 之间的整数。 对 $i = 1, 2, \ldots, N$,第 $i$ 个球上写着的整数是 $A_i$。

当盒子中还有两个或更多个球时,高桥君会重复以下操作。

• 首先,任意选择两个球。
• 然后,设这两个球上写着的整数分别为 $x$ 和 $y$,获得 $x^y + y^x$ 除以 $M$ 的余数作为分数。
• 最后,任意选择其中一个球吃掉,把另一个球放回盒子。

求高桥君能获得的总分数的最大值。

输入格式

输入按以下格式从标准输入给出。

$N$ $M$
$A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出答案。

样例

4 10
4 2 3 2

20

考虑如下的操作过程。下面,$X \bmod Y$ 表示非负整数 $X$ 除以正整数 $Y$ 所得的余数。

先从盒子中取出第 1 个和第 3 个球,获得 $(4^3 + 3^4) \bmod 10 = 5$ 分。然后吃掉第 1 个球,把第 3 个球放回。此时盒子中有第 2、第 3、第 4 个球。

再取出第 3 个和第 4 个球,获得 $(3^2 + 2^3) \bmod 10 = 7$ 分。然后吃掉第 3 个球,把第 4 个球放回。此时盒子中有第 2 和第 4 个球。

再取出第 2 个和第 4 个球,获得 $(2^2 + 2^2) \bmod 10 = 8$ 分。然后吃掉第 2 个球,把第 4 个球放回。此时盒子中只剩下第 4 个球。

此时高桥君共获得 $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

数据范围

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