D - XXOR

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400

問題文

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 bab のビットごとの排他的論理和を表します。

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)。

制約

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

入力

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

N K
A_1 A_2 ... A_N

出力

f の最大値を出力せよ。


入力例 1

3 7
1 6 3

出力例 1

14

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


入力例 2

4 9
7 4 0 3

出力例 2

46

入力例 3

1 0
1000000000000

出力例 3

1000000000000

Score : 400 points

Problem Statement

You are given N non-negative integers A_1, A_2, ..., A_N and another non-negative integer K.

For a integer X between 0 and K (inclusive), let f(X) = (X XOR A_1) + (X XOR A_2) + ... + (X XOR A_N).

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

Find the maximum value of f.

What is XOR?

The bitwise exclusive OR of a and b, X, is defined as follows:

  • When X is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if, when written in base two, exactly one of A and B has 1 in the 2^k's place, and 0 otherwise.

For example, 3 XOR 5 = 6. (When written in base two: 011 XOR 101 = 110.)

Constraints

  • All values in input are integers.
  • 1 \leq N \leq 10^5
  • 0 \leq K \leq 10^{12}
  • 0 \leq A_i \leq 10^{12}

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 ... A_N

Output

Print the maximum value of f.


Sample Input 1

3 7
1 6 3

Sample Output 1

14

The maximum value is: f(4) = (4 XOR 1) + (4 XOR 6) + (4 XOR 3) = 5 + 2 + 7 = 14.


Sample Input 2

4 9
7 4 0 3

Sample Output 2

46

Sample Input 3

1 0
1000000000000

Sample Output 3

1000000000000