XXOR

题目描述

给定 $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$ 的最大值。

样例

3 7
1 6 3

14

$f(4) = (4$ XOR $1) + (4$ XOR $6) + (4$ XOR $3) = 5 + 2 + 7 = 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}$