Problem:
 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 .)

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
k=bin(k)[2:]
p=[0]*40
for i,x in enumerate(a):
  for j in range(40):
    p[-1-j]+=(x>>j)&1
d=2**39
flag=1
b=0
for i in p[:-len(k)]:
  b+=i*d
  d//=2
ans=0
for i,x in enumerate(k):
  if x=='0':continue
  dy=d
  c=0
  for j,(y,z) in enumerate(zip(p[-len(k):],k)):
    if j<i:c+=[y,n-y][z=='1']*dy
    if j==i:c+=y*dy
    if j>i:c+=max(y,n-y)*dy
    dy//=2
  ans=max(ans,b+c)
c=0
for y,z in zip(p[-len(k):],k):
  c+=[y,n-y][z=='1']*d
  d//=2
print(max(ans,b+c))

Solution (Python):
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter



input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

class BIT():
    
    def __init__(self, n):
        self.n = n
        self.BIT = [0] * (n + 2)

    
    def query(self, idx):
        res_sum = 0
        while idx > 0:
            res_sum += self.BIT[idx]
            idx -= idx & (-idx)
        return res_sum

    
    def update(self, idx, x):
        
        while idx <= self.n:
            
            self.BIT[idx] += x
            idx += idx & (-idx)
        return

    def show(self):
        print(self.BIT)


def solve():
    n, k = getList()
    lis = getList()
    ans = 0
    bind = True
    dp = [-1 ,0]
    for rui in range(50, -1, -1):
        tmp = [-1 ,0]
        tgt = pow(2, rui)
        bit = tgt & k
        u, d = 0, 0
        for num in lis:
            if num & tgt == tgt:
                u += 1
            else:
                d += 1
        
        if bit == 0:
            tmp[1] = dp[1] + tgt * u
            if dp[0] != -1:
                tmp[0] = dp[0] + tgt * max(u, d)
        else:
            if dp[0] != -1:
                tmp[0] = dp[0] + tgt * max(u, d)
            tmp[0] = max(dp[1] + tgt * u, tmp[0])
            tmp[1] = dp[1] + tgt * d
        dp = tmp
        
    print(max(dp))

def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    
    solve()

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[]
L=len(bin(k))-2
for x in a:
	b.append(bin(x)[2:])
	L=max(L,len(bin(x))-2)
for i in range(n):
	b[i]="0"*(L-len(b[i]))+b[i]
X=0
for i in range(L):
	if 2**(L-i-1)<=k:
		one=0
		for j in range(n):
			if b[j][i]=="1":
				one+=1
		if one<n-one:
			k-=2**(L-i-1)
			X+=2**(L-i-1)
ans=0
for x in a:
	ans+=X^x
print(ans)

Solution (Python):
import numpy as np

n, k = map(int, input().split())
a = np.array(list(map(int, input().split())))

L = len(f'{10**12:b}')
dp = np.full((L+1, 2), -1, dtype=np.int64)
dp[0, 0] = 0
for i in range(L):
    d = 1 << (L-i-1)
    cnt = np.count_nonzero(a & d)
    val0 = d * cnt
    val1 = d * (n - cnt)

    if dp[i, 1] != -1:
        dp[i+1, 1] = max(dp[i+1, 1], dp[i, 1] + max(val0, val1))
    if dp[i, 0] != -1:
        if k & d:
            dp[i+1, 1] = max(dp[i+1, 1], dp[i, 0] + val0)
    if dp[i, 0] != -1:
        if k & d:
            dp[i+1, 0] = max(dp[i+1, 0], dp[i, 0] + val1)
        else:
            dp[i+1, 0] = max(dp[i+1, 0], dp[i, 0] + val0)

print(max(dp[L, 0], dp[L, 1]))

Solution (Python):
import numpy as np

n, k = map(int, input().split())
a = np.array(list(map(int, input().split())))

L = len(f'{10**12:b}')
res = 0
for i in range(-1, L):
    if i != -1 and not (k >> i) & 1:
        continue
    val = 0
    for j in range(L):
        d = np.count_nonzero((a >> j) & 1)
        if i < j:
            if (k >> j) & 1:
                val += (n-d) * 2**j
            else:
                val += d * 2**j
        elif i == j:
            val += d * 2**j
        else:
            val += max(d, n-d) * 2**j
    res = max(res, val)
print(res)

Solution (Python):
N, K = map(int, input().split())
L = K.bit_length()
D = [0]*(L+1)
A = list(map(int, input().split()))
res=0
for a in A:
    for i in range(L+1):
        D[i] += (a>>i)&1
for i in reversed(range(L+1)):
    if D[i]*2<=N and res+(1<<i)<=K:
        res+=(1<<i)
print(sum(a^res for a in A))

Solution (Python):
N, K = map(int, input().split())
L = K.bit_length()
D = [0]*(L+1)
A = list(map(int, input().split()))
for a in A:
    for i in range(L+1):
        D[i] += (a>>i)&1
res = 0
flg = True
for i in reversed(range(L+1)):
    if flg == False:
        if D[i]<=N//2:
            res += (N-D[i])*pow(2,i)
        else:
            res += D[i]*pow(2, i)
    else:
        if D[i]<=N//2:
            if (K>>i)&1==1:
                res += (N-D[i])*pow(2, i)
            else:
                res += D[i]*pow(2, i)
        else:
            if (K>>i)&1==1:
                flg = False
            res += D[i]*pow(2, i)
mask = 0
for i in range(L+1,43):
    mask += 1<<i
for a in A:
    res += a&mask
print(res)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = list(map(int, input().split()))
a = list(map(int, input().split()))
l = k.bit_length()
vs = [0]*(l)
for i in range(l):
    tmp = sum((item&(1<<i)) for item in a)
    if n*(1<<i) >= 2*tmp:
        vs[i] = n*(1<<i) - 2*tmp
ans = 0
tmp = 0
for i in range(l-1, -1, -1):
    if (k>>i)&1:
        ans = max(ans, tmp+sum(vs[:i]))
        tmp += vs[i]
ans = max(ans, tmp)
print(ans+sum(a))

Solution (Python):
import sys
from functools import lru_cache

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def score(x, counter, N):
    ans = 0
    for i in range(40):
        if x & (1 << i):
            ans += (N - counter[i]) * (1 << i)
        else:
            ans += counter[i] * (1 << i)
    return ans


def main():
    N, K, *A = map(int, read().split())

    counter = [0] * 40
    for a in A:
        for i in range(40):
            if a & (1 << i):
                counter[i] += 1

    B = [0] * 40
    for i in range(39):
        if counter[i] < N - counter[i]:
            B[i + 1] = B[i] + (1 << i)
        else:
            B[i + 1] = B[i]

    C = [0] * 40
    for i in range(39, 0, -1):
        if K & (1 << i):
            C[i - 1] = C[i] + (1 << i)
        else:
            C[i - 1] = C[i]

    ans = score(K, counter, N)

    for i in range(40):
        if K & (1 << i):
            x = B[i] + C[i]
            res = score(x, counter, N)
            if ans < res:
                ans = res

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from functools import lru_cache

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K, *A = map(int, read().split())

    counter = [0] * 40
    for a in A:
        for i in range(40):
            if a & (1 << i):
                counter[i] += 1

    B = [0] * 40
    for i in range(39):
        if counter[i] < N - counter[i]:
            B[i + 1] = B[i] + (1 << i)
        else:
            B[i + 1] = B[i]

    C = [0] * 40
    for i in range(39, 0, -1):
        if K & (1 << i):
            C[i - 1] = C[i] + (1 << i)
        else:
            C[i - 1] = C[i]

    ans = 0
    for a in A:
        ans += K ^ a

    for i in range(40):
        if K & (1 << i):
            x = B[i] + C[i]
            res = 0
            for a in A:
                res += x ^ a
            if ans < res:
                ans = res

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from functools import lru_cache

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K, *A = map(int, read().split())

    counter = [0] * 40
    for a in A:
        for i in range(40):
            if a & (1 << i):
                counter[i] += 1

    Y = 0
    for i in range(39, -1, -1):
        Y <<= 1
        if counter[i] < N - counter[i]:
            Y += 1

    ans = 0
    for a in A:
        ans += K ^ a
    for i in range(40):
        if K & (1 << i):
            x = ((K >> (i + 1)) << (i + 1)) + Y % (1 << i)
            res = 0
            for a in A:
                res += x ^ a
            if ans < res:
                ans = res

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from functools import lru_cache

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K, *A = map(int, read().split())

    K = list(map(int, f'{K:>040b}'))
    A_bin = [list(map(int, f'{a:>040b}')) for a in A]

    B = [0] * 40
    for a in A_bin:
        for i, bit in enumerate(a):
            B[i] += bit

    B = [1 if b < N - b else 0 for b in B]

    @lru_cache(maxsize=None)
    def rec(i, x, smaller):
        if i == 40:
            ans = 0
            for a in A:
                ans += x ^ a
            return ans
        elif smaller:
            return rec(i + 1, (x << 1) + B[i], True)
        elif K[i] <= B[i]:
            return rec(i + 1, (x << 1) + K[i], False)
        else:
            return rec(i + 1, (x << 1) + B[i], True)

    print(rec(0, 0, False))
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from functools import lru_cache

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K, *A = map(int, read().split())

    K = list(map(int, f'{K:>040b}'))
    A2 = [list(map(int, f'{a:>040b}')) for a in A]
    B = [0] * 40
    for a in A2:
        for i, bit in enumerate(a):
            B[i] += bit
    for i in range(40):
        if B[i] == N - B[i]:
            B[i] = 2
        elif B[i] < N - B[i]:
            B[i] = 1
        else:
            B[i] = 0

    @lru_cache(maxsize=None)
    def rec(i, x, smaller):
        if i == 40:
            ans = 0
            for a in A:
                ans += x ^ a
            return ans
        elif smaller:
            if B[i] == 2:
                return rec(i + 1, (x << 1), True)
            else:
                return rec(i + 1, (x << 1) + B[i], True)
        else:
            if B[i] == 2:
                if K[i] == 0:
                    return rec(i + 1, (x << 1), False)
                else:
                    return rec(i + 1, (x << 1), True)
            elif K[i] == B[i]:
                return rec(i + 1, (x << 1) + K[i], False)
            elif K[i] < B[i]:
                return rec(i + 1, (x << 1) + K[i], False)
            else:
                return rec(i + 1, (x << 1) + B[i], True)

    print(rec(0, 0, False))
    return


if __name__ == '__main__':
    main()

Solution (Python):
n,k,*a=map(int,open(0).read().split())
d=[0]*41 
for i in range(n):
  for j in range(41):
    d[j]+=(a[i]>>j)&1
f=0
la=len(bin(max(a)))-2 
lk=len(bin(k))-2 
b=[0]*41 


for i in range(lk-1,-1,-1):
  if (k>>i)&1==1:
    if d[i]<n-d[i]:
      b[i]=1
    else:
      b[i]=0
      f=1
  if (k>>i)&1==0:
    if d[i]<n-d[i] and f==1:
      b[i]=1
    else:
      b[i]=0
ans=0

for i in range(max(lk,la)):
  ans+=(1<<i)*[d[i],n-d[i]][b[i]]
print(ans)

Solution (Python):
n,k,*a=map(int,open(0).read().split())
d=[0]*41
for i in range(n):
  for j in range(41):
    d[j]+=(a[i]>>j)&1
f=0
la=len(bin(max(a)))-2
lk=len(bin(k))-2
b=[0]*41
for i in range(lk-1,-1,-1):
  if (k>>i)&1==1:
    if d[i]<n-d[i]:
      b[i]=1
    else:
      b[i]=0
      f=1
  if (k>>i)&1==0:
    if d[i]<n-d[i] and f==1:
      b[i]=1
    else:
      b[i]=0
ans=0
for i in range(max(lk,la)):
  ans+=(1<<i)*[d[i],n-d[i]][b[i]]
print(ans)

Solution (Python):
n,k,*a=map(int,open(0).read().split())
d=[0]*41 
for i in range(n):
  for j in range(41):
    d[j]+=(a[i]>>j)&1
f=0
la=len(bin(max(a)))-2
lk=len(bin(k))-2
b=[0]*41
for i in range(lk-1,-1,-1):
  if (k>>i)&1==1:
    if d[i]<n-d[i]:
      b[i]=1
    else:
      b[i]=0
      f=1
  if (k>>i)&1==0:
    if d[i]<n-d[i] and f==1:
      b[i]=1
    else:
      b[i]=0
ans=0
for i in range(max(lk,la)):
  ans+=(1<<i)*[d[i],n-d[i]][b[i]]
print(ans)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
zero_count = [0 for i in range(50)]
for x in A:
    for i in range(50):
        zero_count[i] += 1 - (x >> i) & 1

ans = sum(A)
res = 0
for x in A:
	res+= (K^x)
ans =max(ans,res)    
K_bit_1 = [False for i in range(50)]
for i in range(49, -1, -1):
    if K >> i & 1:
        K_bit_1[i] = True

for x in range(50):
    if K_bit_1[x] == True:
        sub_ans = 0
        for i in range(49, x, -1):
            if K_bit_1[i]:
                sub_ans += (zero_count[i])*(1 << i)
            else:
                sub_ans += (N-zero_count[i])*(1 << i)
        sub_ans += (N-zero_count[x])*(1 << x)
        for j in range(x-1, -1, -1):
            sub_ans += max(N-zero_count[j], zero_count[j])*(1 << j)
        ans = max(sub_ans, ans)
print(ans)

Solution (Python):
import sys

input = sys.stdin.readline


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    K_d = [0] * (len(bin(10 ** 12)) - 2)
    L = len(K_d)
    for i, k in enumerate(bin(K)[2:][::-1], 1):
        k = int(k)
        K_d[L - i] = k

    cnt_d = [[0, 0] for _ in range(L)]
    for a in A:
        for i in range(L - 1, -1, -1):
            cnt_d[i][a & 1] += 1
            a >>= 1

    ans = 0
    lower_K = False
    for i, (d, (n_zero, n_one)) in enumerate(zip(K_d, cnt_d)):
        if n_zero <= n_one:
            n = 0
        else:
            n = 1
        
        if not lower_K:
            if d == 1 and n == 0:
                lower_K = True
            elif d == 0 and n == 1:
                n = 0

        num = cnt_d[i][n ^ 1]
        ans += num * 2 ** (L - 1 - i)

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
N,K = map(int,input().split())
A = list(map(int,input().split()))
x = 50
lst1 = [0]*x
lst0 = [0]*x
for i in range(x):
    for Ai in A:
        if Ai >> i & 1:
            lst1[i] += 1
        else:
            lst0[i] += 1
dp = [[0,0] for _ in range(x)] 
dp[x-1][1] = -1
for i in range(x-1)[::-1]:
    if K >> i & 1:
        if dp[i+1][1] == -1:
            dp[i][1] = lst1[i]*(1 << i)
        else:
            dp[i][1] = max((dp[i+1][1]+lst0[i]*(1 << i)),dp[i+1][0]+lst1[i]*(1 << i))
        dp[i][0] = dp[i+1][0]+max(lst1[i],lst0[i])*(1 << i)
    else:
        if dp[i+1][1] == -1:
            dp[i][1] = -1
            dp[i][0] = dp[i+1][0]+lst1[i]*(1 << i)
        else:
            dp[i][1] = dp[i+1][1]+max(lst1[i],lst0[i])*(1 << i)
            dp[i][0] = max(dp[i+1][0]+lst1[i]*(1 << i),dp[i+1][1]+lst0[i]*(1 << i))
print(dp[0][0])

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))

def f(x, n):
  i = 0
  while x != 0:
    cnt_bit[i] +=  x % abs(n)
    if n < 0:
      x = - ( (-x)//n )
    else:
      x //= n
    i += 1

def base(x, n):
  ret = []
  while x != 0:
    ret.append( x % abs(n))
    if n < 0:
      x = - ( (-x)//n )
    else:
      x //= n
  return ret

cnt_bit = [0]*50
Flag = True

for a in A:
  f(a, 2)

B = base(K, 2)
M = len(B)

for i in range(M):
  c1, c0 = cnt_bit[M-1-i], N - cnt_bit[M-1-i]
  if Flag:
    if c1 >= c0:
      if B[M-1-i] == 1:
        Flag = False
      B[M-1-i] = 0
  else:
    if c1 >= c0:
      B[M-1-i] = 0
    else:
      B[M-1-i] = 1

if K == 0:
  k = 0
else:
  k = int("".join(map(str, reversed(B))), 2)

ans = 0
for a in A:
  ans += a^k

print(ans)

Solution (Python):
N,K = map(int,input().split())
A = list(map(int,input().split()))
for i in range(N):
    A[i] = format(A[i],'050b')

K = format(K,'050b')
lis = [[0] * 2 for i in range(51)]
for i in range(50):
    for j in range(N):
        lis[i+1][int(A[j][i])] += 1
    lis[i+1].reverse()



dp = [[-1] * 2 for  i in range(51)]
dp[0][0] = 0
for i in range(50):
    nd = int(K[i])
    for j in range(2):
        if dp[i][j] == -1:
            continue
        for d in range(2):
            ni = i+1
            nj = j
            if j == 0:
                if d > nd:
                    continue
                if d < nd:
                    nj = 1
            dp[ni][nj] = max(dp[ni][nj],dp[i][j] + (lis[ni][d] * 2**(49-i)))


print(max(dp[50][0],dp[50][1]))

Solution (Python):
from collections import defaultdict

N,K = map(int, input().split())
A = list(map(int, input().split()))
BMAX = 40
"""
・K以下の非負整数の範囲で〜：桁DP感ある
・XORをとる：桁ごとに確認できる
・Xを選んで、f = X xor A1 + X xor A2 + ... + X xor AN
　 -> それぞれのAと毎回 xor 取るのではなく、桁ごとに xor を取ることができる　←　超重要のはず
　 -> A1 ~ AN の各桁（2進数の時の）に1が立っているのが何個あるか数えておく


遷移
dp[i][1] -> dp[i+1][1] : i-1桁目まででK未満が確定していれば、i桁目に1,0どちらを選んでもK未満
dp[i][0] -> dp[i+1][1]  : i-1桁目まででKと一致している場合、Kのi桁目が1なら、Xで0を選べば遷移できる
dp[i][0] -> dp[i+1][0]  : i桁目まで一致させる場合
"""

d = [0] * BMAX
for a in A:
  for i in range(BMAX):
    if a & (1 << i):
      d[i] += 1




dp = [[-1 for _ in range(2)] for _ in range(BMAX+1)]


dp[0][0] = 0

for i in range(BMAX):
  now = BMAX-1-i
  
  p0 = (2**now) * d[now]
  p1 = (2**now) * (N - d[now])
  
  
  if K & (1 << now):
    is_one = True
  else:
    is_one = False

  
  if dp[i][1] != -1:
    dp[i+1][1] = dp[i][1] + max(p1, p0)

  
  if dp[i][0] != -1 and is_one:
    dp[i+1][1] = max(dp[i+1][1], dp[i][0] + p0)

  
  if dp[i][0] != -1:
    dp[i+1][0] = dp[i][0] + (p1 if is_one else p0)    

print(max(dp[-1]))

Solution (Python):
from collections import defaultdict

N,K = map(int, input().split())
A = list(map(int, input().split()))
BMAX = 40
"""
・K以下の非負整数の範囲で〜：桁DP感ある
・XORをとる：桁ごとに確認できる
・Xを選んで、f = X xor A1 + X xor A2 + ... + X xor AN
　 -> それぞれのAと毎回 xor 取るのではなく、桁ごとに xor を取ることができる　←　超重要のはず
　 -> A1 ~ AN の各桁（2進数の時の）に1が立っているのが何個あるか数えておく


遷移
dp[i][1] -> dp[i+1][1] : i-1桁目まででK未満が確定していれば、i桁目に1,0どちらを選んでもK未満
dp[i][0] -> dp[i+1][1]  : i-1桁目まででKと一致している場合、Kのi桁目が1なら、Xで0を選べば遷移できる
dp[i][0] -> dp[i+1][0]  : i桁目まで一致させる場合
"""

d = [0] * BMAX
for a in A:
  for i in range(BMAX):
    if a & (1 << i):
      d[i] += 1




dp = [[-1 for _ in range(2)] for _ in range(BMAX+1)]


dp[0][0] = 0

for i in range(BMAX):
  now = BMAX-1-i
  
  p0 = (2**now) * d[now]
  p1 = (2**now) * (N - d[now])
  
  
  if K & (1 << now):
    is_one = True
  else:
    is_one = False

  
  if dp[i][1] != -1:
    dp[i+1][1] = dp[i][1] + max(p1, p0)

  
  if dp[i][0] != -1 and is_one:
    dp[i+1][1] = max(dp[i+1][1], dp[i][0] + p0)

  
  if dp[i][0] != -1:
    dp[i+1][0] = dp[i][0] + (p1 if is_one else p0)    

print(max(dp[-1]))

Solution (Python):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def solve(N, W, ws, vs):
    
    *S, = zip(vs, ws)

    def make(S):
        T = {0: 0}
        for v, w in S:
            
            T0 = dict(T)
            for k, val in T.items():
                if k + w > W:
                    continue
                if k + w in T0:
                    T0[k + w] = max(T0[k + w], val + v)
                else:
                    T0[k + w] = val + v
            T = T0
        v = 0
        R = []
        for k in sorted(T):
            v = max(v, T[k])
            
            R.append((k, v))
        return R

    def solve(T0, T1):
        T0.sort()
        T1.sort(reverse=1)

        it = iter(T1)
        k1, v1 = next(it)
        yield 0
        for k0, v0 in T0:
            
            while k0 + k1 > W:
                k1, v1 = next(it)
            yield v0 + v1

    
    T0 = make(S[:N // 2])
    T1 = make(S[N // 2:])

    
    return max(solve(T0, T1))


def main():

    N, K = in_nn()
    A = in_nl()

    max_num = max(K, max(A))
    bit_len = max_num.bit_length()

    ws = []
    vs = []

    sum_value = 0
    for i in range(bit_len):

        cnt = 0
        for j in range(N):
            cnt += (A[j] >> bit_len - i - 1) & 1

        n = 2 ** (bit_len - i - 1)
        if cnt < -(-N // 2):
            value = (N - 2 * cnt) * n
            weight = n
            vs.append(value)
            ws.append(weight)
        sum_value += cnt * n

    ret = solve(len(vs), K, ws, vs)
    print(sum_value + ret)


if __name__ == '__main__':
    main()

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))

A_max = max(A)

M = len(bin(A_max)) - 2
L = len(bin(K)) - 2
C = [[N, 0] for j in range(max(M, L))]
for i in A:
    for j in range(M):
        if (i >> j) & 1:
            C[j][1] += 1
            C[j][0] -= 1

P = 0
for j in range(L-1, -1, -1):
    if C[j][0] >= C[j][1]:
        if P + 2 ** j <= K:
            P += 2 ** j

ans = 0
for i in A:
    ans += P ^ i

print(ans)

Solution (Python):
import sys
import math
import collections
import bisect
import copy



sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))





def main():
    n, k = ns()
    a = na()

    max_len = 41
    popcount = [0] * max_len

    for ai in a:
        cnt = 0
        while ai > 0:
            if ai & 1:
                popcount[cnt] += 1
            ai >>= 1
            cnt += 1
    popcount.reverse()

    dp1 = [0 for _ in range(max_len + 1)]
    dp2 = [-1 for _ in range(max_len + 1)]

    for i in range(max_len):
        tmp = pow(2, max_len - 1 - i)
        ki = k >> (max_len - 1 - i) & 1

        one = popcount[i]
        zero = n - popcount[i]

        if ki:
            dp1[i + 1] = dp1[i] + zero * tmp
            dp2[i + 1] = dp1[i] + one * tmp
            if dp2[i] != -1:
                dp2[i+1] = max(dp2[i+1], dp2[i] + zero * tmp, dp2[i] + one * tmp)

        else:
            dp1[i + 1] = dp1[i] + one * tmp
            if dp2[i] != -1:
                dp2[i + 1] = max(dp2[i] + zero * tmp, dp2[i] + one * tmp)

    print(max(dp1[max_len], dp2[max_len]))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = list(map(int, input().split()))
L = 50
dp = [[-float('inf')]*2 for _ in range(L+1)]
dp[0][0] = 0

for i in range(L):
    Ki = (K>>(L-1-i))&1
    
    for j in range(2):
        for k in range(2 if j else Ki+1):
            add = 0
            
            for Ai in A:
                add += k^((Ai>>(L-1-i))&1)
            
            dp[i+1][j|(k<Ki)] = max(dp[i+1][j|(k<Ki)], dp[i][j]+add*2**(L-1-i))
            
print(max(dp[L]))

Solution (Python):
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = list(map(int, input().split()))
L = 100
dp = [[-float('inf')]*2 for _ in range(L+1)]
dp[0][0] = 0

for i in range(L):
    Ki = (K>>(L-1-i))&1
    
    for j in range(2):
        for k in range(2 if j else Ki+1):
            add = 0
            
            for Ai in A:
                add += k^((Ai>>(L-1-i))&1)
            
            dp[i+1][j|(k<Ki)] = max(dp[i+1][j|(k<Ki)], dp[i][j]+add*2**(L-1-i))
            
print(max(dp[L]))

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





N, K = getNM()
A = getList()









flag = [0] * 61
def splitbit(n):
    for i in range(61):
        if n & (1 << i):
            flag[i] += 1
for i in range(N):
    splitbit(A[i])

x = 0
ans = 0
for i in range(60, -1, -1):
    
    
    
    if flag[i] < N - flag[i] and x + 2 ** i <= K:
        
        x += 2 ** i
        
        ans += 2 ** i * (N - flag[i])
    
    
    else:
        ans += 2 ** i * flag[i]

print(ans)

Solution (Python):
n,k = map(int,input().split())
a = list(map(int,input().split()))
l = [[0,0] for _ in range(40)]
for i in range(n):
    for j in range(40):
        l[j][a[i] >> j & 1] += 1
lst = [0]*41
for i in range(40):
    lst[i+1] = lst[i] + max(l[i])*2**i
l2 = [k >> j & 1 for j in range(40)]
lst2 = [0]*41
for i in range(39,-1,-1):
    lst2[i] = lst2[i+1]+l[i][1-l2[i]]*(2**i)
ans = lst2[0]
for i in range(40):
    if l2[i] == 0:
        continue
    t = lst2[i+1] + l[i][1]*(2**i) + lst[i]
    ans = max(t,ans)
print(ans)

Solution (Python):
import numpy as np

st = lambda n: bin(n)[2:]
N,K = map(int,input().split())
a = np.array([int(i) for i in input().split()])

MAX = 10**12
mm = MAX.bit_length()
chk = [((a >> K) & 1).sum() for K in range(mm)]

ll = []
q = 0
for num,cc in enumerate(chk):
  if cc < N/2:
    q += 2**(num)
  ll.append((num,2**num*(N-cc),2**num*cc))
    
max_V = 0
KK = (K+1).bit_length()
sk = st(K+1).zfill(mm)
sq = st(q).zfill(mm)

for i in range(KK):
  if (K+1)>>i&1 == 1:
    op = q
    if q>>i&1 == 1:
      op -= 2**i
    I = KK-i
    for j in range(mm-KK+I):
      if sq[j] == '1' and sk[j] == '0':
        op -= 2**(mm-1-j)
    V = 0
    for nm,v_1,v_0 in ll:
      if op>>nm & 1 == 1:     
        V += v_1
      else:
        V += v_0
    max_V = max(max_V, V)
    
print(max_V)

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))

max_digit = K.bit_length()

def bi(x,max_d=max_digit):
  b = bin(x)[2:]
  if len(b) < max_d:
    return '0'*(max_d-len(b))+b
  else:
    return b[-max_digit:]
  
def f(x):
    return sum(map(lambda a:a^x, A))

B = list(map(bi,A))

count = [0]*max_digit
ans=0
for j in range(max_digit):
  for i in range(N):
    if B[i][j]=='1':count[j]+=1
  if count[j]<N/2:
    if ans + 2**(max_digit-j-1) <= K:
      ans += 2**(max_digit-j-1)
    else:
      continue

print(f(ans))

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



N, K = MAP()
A = LIST()
 
n = max(A+[K]).bit_length()
cnt = [0]*n
 
for a in A:
	for i in range(n):
		if a & (1<<i):
			cnt[i] += 1

X = 0
for i in range(n-1, -1, -1):
	if X + (1<<i) <= K and cnt[i] <= (N-1)//2:
		X += (1<<i)
 

ans = 0
for a in A:
	ans += a^X
 
print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



N, K = MAP()
A = LIST()
tmp = [0]*40

for a in A:  
	for i in range(40):
		if a&(1<<i):
			tmp[i] += 1

a = 0
for i in range(39, -1, -1):
	if a + (1<<i) <= K and tmp[i] < (N+1)//2:
		a += 1<<i

ans = 0
for i in A:
	ans += i^a
print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



N, K = MAP()
A = LIST()

n = max(A+[K]).bit_length()
cnt = [[0, 0] for _ in range(n)]

for a in A:
	b = "{:b}".format(a).zfill(n)[::-1]
	for i in range(n):
		cnt[i][int(b[i])] += 1

max_X = []
for cnt_0, cnt_1 in cnt:
	if cnt_0 <= cnt_1:
		max_X.append(0)
	else:
		max_X.append(1)
max_X = max_X[::-1]     

k = "{:b}".format(K).zfill(n)

if len(k) == n:
	for i in range(n):
		if int(k[i]) > max_X[i]:
			break
		elif int(k[i]) < max_X[i]:
			max_X[i] = 0

X = 0
for i, p in enumerate(max_X[::-1]):
	X += 2**i*p


ans = 0
for a in A:
	ans += a^X

print(ans)