吃球有方

题目描述

$n$ 个球，第 $i$ 个球上面有一个数字 $a_i$，球球间会互相吞噬，每次可以任意选择两个球 ，表示 $x$ 吞噬了 $y$，这样会产生 $(a_x+a_y+(a_x \oplus a_y))\bmod M$（ $\oplus$ 表示异或） 的贡献，并且会使得 $y$ 消失。不断选择，直到只剩下一个球，求最大贡献。

输入格式

第一行，两个数 $n,M$

第二行，$n$ 个数，表示每个球上面的数字$a_i$

输出格式

一个数，表示最大贡献

数据范围

对于所有数据，$2\le n\le 500,2\le M\le 10^9,1\le a_i\le M$

样例

1.输入

4 10 4

4 2 3 2

1.输出

16

2.输入

20 100

29 31 68 20 83 66 23 84 69 96 41 61 83 37 52 71 18 55 40 8

2.输出

1522