/ 
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 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)。
制約
- 入力は全て整数である
- 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