Caique, o guloso

O menino Caique está com fome e possui uma caixa com $N$ bolas numeradas de $1$ a $M-1$. Cada bola i possui um número $A_i$.

Enquanto a caixa tiver pelo menos duas bolas, Caique irá repetir o seguinte procedimento:

1. Escolherá duas bolas arbitrariamente.
2. Receberá uma pontuação igual ao resto da divisão de $X^Y + Y^X$ por $M$, onde $X e Y$ são os números escritos nas duas bolas escolhidas.
3. Escolherá uma das duas bolas, comerá a bola escolhida e devolverá a outra bola para a caixa.

Imprima a pontuação total máxima que Caique pode obter.

Restrições:

• $2 \le N \le 500$
• $2 \le M \le 10^9$
• $1 \le A_i \le M-1$
• Todos os valores na entrada são inteiros.

Entrada

A entrada é dada em uma única linha no seguinte formato: $N M A_1 A_2 ... A_N$

Saída

Imprima a resposta.

Exemplos

20

Explicação: Caique escolhe a primeira e a terceira bola, obtendo uma pontuação de $(4^3 + 3^4) % 10 = 5$. Ele come a primeira bola e devolve a terceira bola para a caixa, que agora contém as bolas 2 e 3. Caique escolhe a terceira e a quarta bola, obtendo uma pontuação de $(3^2 + 2^3) % 10 = 7$. Ele come a terceira bola e devolve a quarta bola para a caixa, que agora contém as bolas 2 e 4. Caique escolhe a segunda e a quarta bola, obtendo uma pontuação de $(2^2 + 2^2) % 10 = 8$. Ele come a segunda bola e devolve a quarta bola para a caixa, que agora contém somente a bola 4. No final, Caique obteve uma pontuação total máxima de $5 + 7 + 8 = 20$.

1733

Para submeter sua solução use esse link.