题目描述

$N$ 個の非負整数 $A_1,\ A_2,\ ...,\ A_N$ および非負整数 $K$ が与えられます。

$0$ 以上 $K$ 以下の整数 $X$ に対して、$f(X)\ =\ (X$ XOR $A_1)$ $+$ $(X$ XOR $A_2)$ $+$ $...$ $+$ $(X$ XOR $A_N)$ とします。

ここで、非負整数 $a,\ b$ に対して $a$ XOR $b$ は $a$ と $b$ のビットごとの排他的論理和を表します。

$f$ の最大値を求めてください。

XOR とは

整数 $A,\ B$ のビットごとの排他的論理和 $X$ は、以下のように定義されます。

• $X$ を二進表記した際の $2^k$ ($k\ \geq\ 0$) の位の数は、$A,\ B$ を二進表記した際の $2^k$ の位の数のうち一方のみが $1$ であれば $1$、そうでなければ $0$ である。

例えば、$3$ XOR $5\ =\ 6$ となります (二進数表記すると: $011$ XOR $101\ =\ 110$)。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $K$ $A_1$ $A_2$ $...$ $A_N$

输出格式

$f$ の最大値を出力せよ。

题目大意

题目描述

有n个数$a_1,a_2……a_n$和一个数k，$\oplus$表示按位异或。对于$0\leq x\leq k，f(x)=(x \oplus a_1)+(x \oplus a_2)……(x \oplus a_n)$。求$f_{max}$为多少。

输入格式

一行两个数n，m，接下来一行m个用空格隔开的整数$x_1,x_2……x_n$。

输出格式

一行一个数表示答案。

数据范围

$1\leq n\leq 10^5,0\leq k,a_i\leq 10^{12}$

3 7
1 6 3

14

4 9
7 4 0 3

46

1 0
1000000000000

1000000000000

提示

制約

• 入力は全て整数である
• $1\ \leq\ N\ \leq\ 10^5$
• $0\ \leq\ K\ \leq\ 10^{12}$
• $0\ \leq\ A_i\ \leq\ 10^{12}$

Sample Explanation 1

$f(4)\ =\ (4$ XOR $1)\ +\ (4$ XOR $6)\ +\ (4$ XOR $3)\ =\ 5\ +\ 2\ +\ 7\ =\ 14$ が最大です。