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.