#ABC117D. XXOR

XXOR

题目描述

You are given NN non-negative integers A1,A2,...,ANA_1, A_2, ..., A_N and another non-negative integer KK.

For a integer XX between 00 and KK (inclusive), let f(X)=(Xf(X) = (X XOR A1)A_1) ++ (X(X XOR A2)A_2) ++ ...... ++ (X(X XOR AN)A_N).

Here, for non-negative integers aa and bb, aa XOR bb denotes the bitwise exclusive OR of aa and bb.

Find the maximum value of ff.

What is XOR?

The bitwise exclusive OR of aa and bb, XX, is defined as follows:

  • When XX is written in base two, the digit in the 2k2^k's place (k0k \geq 0) is 11 if, when written in base two, exactly one of AA and BB has 11 in the 2k2^k's place, and 00 otherwise.

For example, 33 XOR 5=65 = 6. (When written in base two: 011011 XOR 101=110101 = 110.)

给你 NN 个非负整数 A1,A2,...,ANA_1, A_2, ..., A_N 和另一个非负整数 KK

对于 00KK 之间的整数 XX (对于介于 00KK 之间的整数 XX ,让 f(X)=(Xf(X) = (X XOR A1)A_1) ++ (X(X XOR A2)A_2) ++ ...... ++ (X(X XOR AN)A_N)

这里,对于非负整数 aabb , aa XOR bb 表示位相除。XOR bb 表示 aabb 的位排他性 OR。

ff 的最大值。

什么是 XOR?

aabb 的比特排他 OR, XX ,定义如下:

  • 当以二进制写入 XX 时,如果在以二进制写入时, AABB 中正好有一个数字在 2k2^k 的位置上有 11 ,那么在 2k2^k 的位置上( k0k \geq 0 )的数字就是 11 ,否则就是 aa

例如, 335=65 = 6 的 xorxor 5=65 = 6 。(以二进制书写时: 011011 XOR 101=110101 = 110 )。

输入格式

输入内容按以下格式标准输入:

NN KK
A1A_1 A2A_2 ...... ANA_N

输出格式

打印 ff 的最大值。

样例 #1

样例输入 #1

3 7
1 6 3

样例输出 #1

14

样例 #2

样例输入 #2

4 9
7 4 0 3

样例输出 #2

46

样例 #3

样例输入 #3

1 0
1000000000000

样例输出 #3

1000000000000

说明

数据规模与约定

  • 所有输入值均为整数。
  • 1N1051 \leq N \leq 10^5
  • 0K10120 \leq K \leq 10^{12}
  • 0Ai10120 \leq A_i \leq 10^{12}

样例 11 解释

最大值是 f(4)=(4f(4) = (4 XOR 1)+(41) + (4 XOR 6)+(46) + (4 XOR 3)=5+2+7=143) = 5 + 2 + 7 = 14