Problem:
 Score : 500 points    Problem Statement Seisu-ya , a store specializing in non-negative integers, sells N non-negative integers. The i -th integer is A_i and has a utility of B_i .
There may be multiple equal integers with different utilities.  Takahashi will buy some integers in this store. He can buy a combination of integers whose bitwise OR is less than or equal to K . He wants the sum of utilities of purchased integers to be as large as possible.  Find the maximum possible sum of utilities of purchased integers.      Constraints  1 \leq N \leq 10^5  0 \leq K < 2^{30}  0 \leq A_i < 2^{30}(1\leq i\leq N)  1 \leq B_i \leq 10^9(1\leq i\leq N)  All input values are integers.         Inputs Input is given from Standard Input in the following format:  N  K  A_1  B_1 : A_N  B_N       Outputs Print the maximum possible sum of utilities of purchased integers.        Sample Input 1 3 5
3 3
4 4
2 5      Sample Output 1 8  Buy 2 and 3 to achieve the maximum possible total utility, 8 .       Sample Input 2 3 6
3 3
4 4
2 5      Sample Output 2 9  Buy 2 and 4 to achieve the maximum possible total utility, 9 .       Sample Input 3 7 14
10 5
7 4
11 4
9 8
3 6
6 2
8 9      Sample Output 3 32

Solution (Python):
n, k = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]

def solve(num):
    res = 0
    for i in range(n):
        if (info[i][0] | num) == num:
            res += info[i][1]
    return res


k = bin(k)[2::]
ans = 0
num = int(k,2)
ans = solve(num)

for i in range(len(k)):
    if k[i] == "1":
        num = int(k[0:i]+"0"+(len(k)-i-1)*"1", 2)
        ans = max(ans, solve(num))
print(ans)

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

N, K = map(int, input().split())
int_list = []
for _ in range(N):
    A, B = map(int, input().split())
    int_list.append([A, B])

K_bin = bin(K)[2:]
max_len = len(K_bin)
for i in range(N):
    int_list[i] = (bin(int_list[i][0])[2:].zfill(max_len), int_list[i][1])

or_list = [K_bin]
for i in range(max_len):
    if K_bin[i] == '1':
        or_list.append(K_bin[:i] + '0' + '1' * (max_len - i - 1))

ans = 0
for k in or_list:
    ans_k = 0
    for A, B in int_list:
        if len(A) > max_len:
            continue
        ok = 1
        for j, a in enumerate(A):
            if a == '1' and k[j] == '0':
                ok = 0
                break
        if ok:
            ans_k += B
    ans = max(ans, ans_k)

print(ans)

Solution (Python):

N,K = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]

AB.sort(key = lambda x:x[0])
import math 

K2 = bin(K)
K2 = K2[2:]

L = len(K2)

ans = 0
zeroidx = [L-i-1 for i in range(len(K2)) if K2[i] == '0']

for a,b in AB:
    if a > K: break
    for z in zeroidx:
        if (a>>z)%2 == 1:
            break
    else:
        ans += b
    
MAX = ans
    


for i in range(len(K2)):
    if K2[i] == '0':continue
    
    Knew2 = K2[:i] +'0' +  ''.join(map(str,['1']*(len(K2)-1-i)))
    Knew = int(Knew2,2)
    zeroidx = [L-i-1 for i in range(len(K2)) if Knew2[i] == '0']
    ans = 0
    for a,b in AB:
        if a > Knew: break
        for z in zeroidx:
            if (a>>z)%2 == 1:
                break
        else:
            ans += b
        
    MAX = max(MAX,ans)
    
print(MAX)

Solution (Python):
n,k = map(int, input().split())
l = [tuple(map(int, input().split())) for _ in range(n)]
k_ = k.bit_length()
ans = sum(b for a,b in l if k|a == k)
for i in range(k_):
  if k&2**i == 0:
    continue
  nk = ((k>>i)<<i) - 1
  ac = 0
  for a,b in l:
    if nk|a == nk:
      ac += b
  if ac > ans:
    ans = ac
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
def calc(k):
    ret=0
    for a,b in AB:
        if a|k==k:
            ret+=b
    return ret

n,k=map(int,input().split())
AB=[tuple(map(int,input().split())) for _ in range(n)]
ans=calc(k)
b=k.bit_length()
for d in range(1,b):
    tmp=k>>d
    if tmp%2==0:
        continue
    tmp<<=d
    tmp-=1
    ans=max(ans,calc(tmp))
print(ans)

Solution (Python):
N,K=map(int,input().split())
A=[]
B=[]
for i in range(N):
	a,b=map(int,input().split())
	A+=a,
	B+=b,
z=0
for i in range(31):
	if K>>i&1 or i==30:
		S=(K>>i<<i)-1if i<30else K
		x=0
		for j in range(N):
			if (S|A[j])==S:
				x+=B[j]
		z=max(z,x)
print(z)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

N,K = map(int,input().split())
A,B = np.array([input().split() for _ in range(N)], dtype=np.int64).T

ks = [K]
x = K
while x:
    ks.append(x-1)
    x -= x&(-x)

answer = 0
for k in ks:
    select = (A & k == A)
    answer = max(answer, B[select].sum())

print(answer)

Solution (Python):
N,K = map(int,input().split())
*AB, = [list(map(int,input().split())) for _ in [0]*N]
bK = bin(K)[2:]
l = len(bK)
def f(x): return sum(b for a,b in AB if a | x == x )

x = ""
ans = f(K)
for k in bK:
    if k=="1":
        n = int((x + "0" + "1"*l)[:l],2)
        ans = max(ans,f(n))
        x+="1"
    else:
        x += "0"

print(ans)

Solution (Python):

n, k = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n)]

ans = 0
for a, b in ab:
    if a | k == k:
        ans += b
for i in range(30):
    if k & 1<<i != 1<<i:
        continue
    
    l = k^(1<<i) | (1<<i) - 1
    
    s = 0
    for a, b in ab:
        if a | l == l:
            s += b
    ans = max(ans, s)
print(ans)

Solution (Python):
N,K=map(int,input().split())
A=[0 for i in range(N)]
B=[0 for i in range(N)]
for i in range(N):
    A[i],B[i]=map(int,input().split())
S=bin(K)
X=[K]
M=len(S)-2
for k in range(1,M+1):
    if S[-k]=="0":continue
    tmp=S[:-k]+"0"+"1"*(k-1)
    X.append(int(tmp,2))
ans=0
for n in X:
    tmp=0
    for i in range(N):
        if A[i]&n==A[i]:
            tmp+=B[i]
    ans=max(ans,tmp)
print(ans)

Solution (Python):
def issubset(x,y):
    
    if len(x)>len(y):
        return False
    for i in range(1,len(x)+1):
        if (x[-i],y[-i])==("1","0"):
            return False
    return True
N,K=map(int,input().split())
A=[0 for i in range(N)]
B=[0 for i in range(N)]
for i in range(N):
    A[i],B[i]=map(int,input().split())
    A[i]=bin(A[i])[2:]
Ks=bin(K)[2:]
Kl=[Ks]
for i,c in enumerate(Ks):
    if c=="1":
        Kl.append(Ks[:i]+"0"+"1"*(len(Ks)-i-1))
ans=0
for k in Kl:
    tmp=0
    for i in range(N):
        if issubset(A[i],k):
            tmp+=B[i]
    ans=max(tmp,ans)
print(ans)

Solution (Python):
import sys
N, K = map(int, input().split())
candi = []
p = 0
for i in range(30, -1, -1):
    if 2**i & K == 0:
        p += 2**i
        continue
    else:
        candi.append(p + 2**i)
candi.append(p)
AB = [tuple(map(int, input().split())) for _ in range(N)]
ans = 0

for c in candi:
    cans = 0
    for a, b in AB:
        if a & c:
            continue
        cans += b
    ans = max(ans, cans)
print(ans)

Solution (Python):
N,K = [ int(it) for it in input().split() ]
li = [ [ int(it) for it in input().split() ] for i in range(N) ]

kbit = []
k = K
for i in range(100000000):
  if (k == 0):
    break
  kbit.append( k%2 )
  k//=2
keta = len(kbit)

def chk(c):
  
  s = 0
  for k,v in li:
    if ( (c^k)|c == c ):
      
      s += v
  return s

ma = 0

if (K<100):
  for i in range(K+1):
  	ma = max(ma, chk(i))
else:
  ma = max(ma, chk( 0 ))
  ma = max(ma, chk( 1 ))
  ma = max(ma, chk( 2 ))
  ma = max(ma, chk( 3 ))
  ma = max(ma, chk( 4 ))
  ma = max(ma, chk( (1<<(keta-1))-1) )
  ma = max(ma, chk ( K ) )

  for i in range(keta):
    if ( kbit[keta-1-i] == 0 ):
      continue
    else:
      bit = [0]*(keta)
      for j in range(keta):
        if (i<j):
          bit[keta-1-j]=1
        elif (j<i):
          bit[keta-1-j]=kbit[keta-1-j]
        else:
          bit[keta-1-j]=0

      v = 0
      for j in range(keta):
        if (bit[j]==1):
          v += 2**(j)
      
      ma = max(ma, chk ( v ) )
print ( ma )

Solution (Python):
N,K=map(int,input().split())
goods=[tuple(map(int,input().split())) for i in range(N)]
ALL=0
from collections import defaultdict
data=defaultdict(int)
B=0
KS=bin(K)[2:]
for a,b in goods:
    astr=bin(a)[2:]
    if len(astr)>len(KS):
        continue
    else:
        B+=b
        for i in range(-1*len(astr),0):
            if astr[i]==KS[i]=="1":
                data[i]+=b
            elif astr[i]=="1" and KS[i]=="0":
                data[i]+=b
                break
ans=0
for i in range(-1*len(KS),0):
    if KS[i]=="1":
        ans=max(B-data[i],ans)
    else:
        B-=data[i]
ans=max(B,ans)
print(ans)

Solution (Python):
n, k = map(int, input().split())
c = []
for i in range(n):
    c.append([int(m) for m in input().split()])

x = 0
candi = [k]
for i in range(31, -1, -1):
    if k & (x + 2 ** i) == x + 2 ** i:
        candi.append(x + 2 ** i - 1)
        x += 2 ** i

ans = 0
tmpans = 0
for can in candi:
    for i in range(n):
        if can & c[i][0] == c[i][0]:
            tmpans += c[i][1]
    ans = max(ans, tmpans)
    tmpans = 0
print(ans)

Solution (Python):
N, K = map(int, input().split())
ABs = [tuple(map(int, input().split())) for _ in range(N)]

ans = 0
for i, b in enumerate(bin(K+1)[2:][::-1]):
    if b == '0': continue
    v = 0
    C = (K+1) & ~((1<<i)-1)
    mask = ~(C-1)
    for A, B in ABs:
        if A < C and A & mask == 0:
            v += B
    ans = max(ans, v)

print(ans)

Solution (Python):
inpl = lambda: list(map(int,input().split()))
N, K = inpl()
A = []
B = []
for _ in range(N):
    a, b = inpl()
    A.append(a)
    B.append(b)

L = K + 1
ans = 0
for i in range(31):
    L_shift = L >> i
    if L_shift & 1 == 0:
        continue
    else:
        L_shift ^= 1
    value = 0
    for j in range(N):
        a_shift = A[j] >> i
        if (a_shift | L_shift) == L_shift:
            value += B[j]
    ans = max(ans,value)

print(ans)

Solution (Python):
import sys
def input():
	return sys.stdin.readline()[:-1]

n, k = map(int, input().split())
d = 31
z = [list(map(int, input().split())) for _ in range(n)]
used = [True for _ in range(n)]
dp = [[0 for _ in range(2)] for _ in range(d)]
dp[d-1][1] = sum([x[1] for x in z])
for i in range(d-2, -1, -1):
	if (k>>i) % 2 == 1:
		dp[i][1] = dp[i+1][1]
		tmp = 0
		for j in range(n):
			if used[j] == True and (z[j][0]>>i) % 2 == 0:
				tmp += z[j][1]
		if tmp == dp[i+1][1]:
			dp[i][1] = 0
			used = [False] * n
		dp[i][0] = max(tmp, dp[i+1][0])
	else:
		dp[i][1] = dp[i+1][1]
		for j in range(n):
			if used[j] == True and (z[j][0]>>i) % 2 == 1:
				used[j] = False
				dp[i][1] -= z[j][1]
		dp[i][0] = dp[i+1][0]
print(max(dp[0]))

Solution (Python):
import sys
def input():
	return sys.stdin.readline()[:-1]

n, k = map(int, input().split())
d = 31
z = [list(map(int, input().split())) for _ in range(n)]
used = [True for _ in range(n)]
dp = [[0 for _ in range(2)] for _ in range(d)]
dp[d-1][1] = sum([x[1] for x in z])
for i in range(d-2, -1, -1):
	if (k>>i) % 2 == 1:
		dp[i][1] = dp[i+1][1]
		tmp = 0
		for j in range(n):
			if used[j] == True and (z[j][0]>>i) % 2 == 0:
				tmp += z[j][1]
		if tmp == dp[i+1][1]:
			dp[i][1] = 0
			used = [False] * n
		dp[i][0] = max(tmp, dp[i+1][0])
	else:
		dp[i][1] = dp[i+1][1]
		for j in range(n):
			if used[j] == True and (z[j][0]>>i) % 2 == 1:
				used[j] = False
				dp[i][1] -= z[j][1]
		dp[i][0] = dp[i+1][0]
print(max(dp[0]))

Solution (Python):

N, K = map(int, input().split())
Items = [list(map(int, input().split())) for i in range(N)]


bs = bin(K)[2:].zfill(31)
masks = [bs]
for k in range(31):
    
    if bs[k] == '1':
        mask = bs[:k] + '0' + '1' * (30 - k)
        masks.append(mask)


ans = 0
for mask in masks:
    mask = int(mask, base=2)
    tmp = 0
    for a, b in Items:
        
        if mask | a == mask:
            tmp += b
    ans = max(ans, tmp)

print(ans)

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,k = li()

ab = []
for _ in range(n):
    a,b = li()
    if a <= k:
        ab.append((a,b))

binn = len(bin(k))-2
bink = bin(k)[2:]


cands = [bink]
for i, s in enumerate(list(bink)):
    if int(s):
        cands.append(bink[:i] + "0" + "1"*(binn-i-1))
        
ans = 0
for cand in cands:
    tmp = 0    
    cand = int("0b"+cand, 0)
    
    for a, b in ab:

        if cand | a <= cand:
            tmp += b
                
    ans = max(ans, tmp)
    
print(ans)

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,k = li()


alis = []
blis = []
for _ in range(n):
    a,b = li()
    if a <= k:
        alis.append(a)
        blis.append(b)

binn = len(bin(k))-2
bink = bin(k)[2:]
binas = [bin(ai)[2:].zfill(binn) for ai in alis]



cands = [bink]
for i, s in enumerate(list(bink)):
    if int(s):
        cands.append(bink[:i] + "0" + "1"*(binn-i-1))
        
ans = 0
for cand in cands:
    tmp = 0    
    cand = int("0b"+cand, 0)
    
    for a, b in zip(alis, blis):

        if cand | a <= cand:
            tmp += b
                
    ans = max(ans, tmp)
    
print(ans)

Solution (Python):
n, k = map(int, input().split())

ab = [[int(i) for i in input().split()] for _ in range(n)]

if k <= 1:
    ans = 0
    for a, b in ab:
        if a <= k:
            ans += b
    print(ans)
    exit()

d = 2
for i in range(31):
    if k < d:
        d //= 2
        break
    d *= 2

ans = 0
for a, b in ab:
    if a | k <= k:
        ans += b

while d > 0:
    temp_k = (k - d) | (d - 1)
    temp_ans = 0
    for a, b in ab:
        if a | temp_k <= temp_k:
            temp_ans += b
    ans = max(ans, temp_ans)
    
    d //= 2

print(ans)

Solution (Python):

import sys
from collections import deque
import copy
import heapq
import math

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, K] = [long(input_raw[0]), long(input_raw[1])]
    A_list = []
    B_list = []
    for i in range(N):
        input_raw = read_func().strip().split()
        [A, B] = [long(input_raw[0]), long(input_raw[1])]
        A_list.append(A)
        B_list.append(B)

    if K == 0:
        value = 0
        for i in range(N):
            if A_list[i] == 0:
                value += B_list[i]
        print value
        exit()
    max_value = 0
    for r in range(int(math.log(K, 2))+1 + 1):
        if ((K>>r) & 0x01) == 1 or r > int(math.log(K, 2)):
            if r <= int(math.log(K, 2)):
                Kr = ((K & ~(0x01<<r)) | ((0x01<<r) - 1))
            else:
                Kr = K
            value = 0
            for i in range(N):

                if (A_list[i] | Kr) == Kr:
                    value += B_list[i]
            max_value = max(max_value, value)

    print max_value



if __name__ == '__main__':
    main()

Solution (Python):
import math

if __name__ == '__main__':
    N, K = list(map(int, input().split()))
    integer_value = []
    for i in range(N):
        integer, value = list(map(int, input().split()))
        integer_value.append((integer, value))
    if K == 0:
        r = 0
    else:
        r = int(math.log(K, 2))
    max_value = 0
    for i in range(r + 1):
        
        if not ((K >> i) & 0b1):
            continue

        tmp_sum = 0

        mask = 1
        for j in range(i):
            mask = (mask << 1) + 1
        Ki = (K | mask) - 2 ** i

        for tmp_int, tmp_val in integer_value:
            if Ki | tmp_int == Ki:
                tmp_sum += tmp_val

        
        if max_value < tmp_sum:
            max_value = tmp_sum

    
    K_val = 0
    for tmp_int, tmp_val in integer_value:
        if K | tmp_int == K:
            K_val += tmp_val
    
    
    if K_val < max_value:
        print(max_value)
    else:
        print(K_val)

Solution (Python):

def get (K):
	ret = [K]
	for r in range(31):
		if ((K >> r) & 1) == 1 :
			tmp = K
			tmp &= (~(1 << r))
			tmp |= (1 << r) - 1
			ret.append(tmp);
	return ret


N, K = map(int, input().split())
items = []
for steps in range(N):
	A, B = map(int, input().split())
	items.append([A, B])

targets = get(K)
answer = 0
for target in targets:
	cur = 0
	for a, b in items:
		if(target | a == target):
			cur += b;
	answer = max(answer, cur)

print(answer)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def pf(s):
    print(s, flush=True)

def main():
    n,k = LI()
    t = [LI() for _ in range(n)]

    d = {}
    d[k] = 0
    j = 0
    for i in range(30,-1,-1):
        ii = 2**i
        if k & ii > 0:
            d[j+ii-1] = 0
            j += ii
    js = d.keys()
    for a,b in t:
        for j in js:
            if j & a ^ a == 0:
                d[j] += b
    return max(d.values())




print(main())

Solution (Python):
N, K = map(int, input().split())
A, B, a = [0] * N, [0] * N, [''] * N
for i in range(N):
    A[i], B[i] = map(int, input().split())
    a[i] = str(bin(A[i])[2:]).rjust(30, '0')
k = str(bin(K)[2:]).rjust(30, '0')

ans = 0

s = k.index('1') if '1' in k else 30
for r in range(s, 30 + 1):
    tmp = 0
    for i in range(N):
        if r < 30 and k[r] == '0':
            continue
        affordable = True
        for j in range(r):
            if k[j] == '0' and a[i][j] == '1':
                affordable = False
        if r < 30 and a[i][r] == '1':
            affordable = False
        if affordable:
            tmp += B[i]
    ans = max(ans, tmp)

print(ans)

Solution (Python):
N,K = map(int,input().split())
items = tuple(tuple(map(int,input().split())) for _ in range(N))

def it():
  i = 1
  while i <= K:
    if K & i:
      j = (K^i)|(i-1)
      yield sum(b for a,b in items if a&~j==0)
    i <<= 1
  yield sum(b for a,b in items if a&~K==0)

print(max(it()))

Solution (Python):

























import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import re
import string

N, K = map(int, input().split())
A = []
B = []
for n in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

ret = 0


for n in range(N):
    if K | A[n] == K:
        ret += B[n]


for i in range(31):
    
    if (K >> i) & 1 == 0:
        K |= (1 << i)
    else:
        
        K ^= (1 << i)

        local_ret = 0
        for n in range(N):
            if K | A[n] == K:
                local_ret += B[n]
        ret = max(ret, local_ret)

        
        K |= (1 << i)


print(ret)

Solution (Python):
N, K = map(int, input().split())
A = [tuple(int(x) for x in input().split()) for _ in range(N)]
A = [(a, b) for a, b in A if a <= K]
L = K.bit_length()
ans = sum(b for a, b in A if (a | K) <= K)
for i in reversed(range(L)):
    bit = (1 << i) & K
    if bit != 1:
        cand = 0
        bor = 0
        tmp_K = K & ~(1 << i) | ((1 << i) - 1)
        ans = max(ans, sum(b for a, b in A if (a | tmp_K) <= K))
print(ans)

Solution (Python):























import array
from bisect import *
from collections import *
import fractions
import heapq 
from itertools import *
import math
import re
import string

N, K = map(int, input().split())
A = []
B = []
for n in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

ret = 0


for n in range(N):
    if K | A[n] == K:
        ret += B[n]


for n in range(31):
    
    if (K >> n) & 1 == 0:
        K |= (1 << n)
    else:
        
        K ^= (1 << n)

        local_ret = 0
        for m in range(N):
            if K | A[m] == K:
                local_ret += B[m]
        ret = max(ret, local_ret)

        
        K |= (1 << n)


print(ret)

Solution (Python):

def inpl(): 
    return tuple(map(int, input().split()))

N, K = inpl()
numbers = []

for _ in range(N):
    A, B = inpl()
    numbers.append([A, B])
res = 0

target = bin(K)[2:]
targets = [target]
while "10" in target:
    n = target.rfind("10")
    new_target = target[:n] + "0" + "1"*(len(target)-n-1)
    targets.append(new_target)
    target = new_target

targets = list(map(int, targets, [2]*len(targets)))

for target in targets:
    tmp = 0
    for a, b in numbers:
        if (target | a) == target:
            tmp += b
    res = max(res, tmp)
print(res)

Solution (Python):


import sys
import math
import copy

N, K = list(map(int, sys.stdin.readline().rstrip().split()))
data = []
for _ in range(N):
    A, B = list(map(int, sys.stdin.readline().rstrip().split()))
    data.append([A, B])

ans = 0


def lower(x, y):
    if(x > y):
        return False
    
    if((x | y) ^ y) == 0:
        return True
    else:
        return False


Nstr = list(reversed(bin(K)[2:]))
subNs = [K]
for i in range(len(Nstr)):
    if Nstr[i] == "0":
        continue
    subNstr = copy.deepcopy(Nstr)
    subNstr[i] = "0"
    for j in range(i):
        subNstr[j] = "1"

    realstr = ""
    for s in reversed(subNstr):
        realstr += s
    subNs.append(int(realstr, 2))


for subNstr in subNs:
    subans = 0
    for A, B in data:
        
        if(lower(A, subNstr)):
            subans += B
    
    ans = max(subans, ans)

print(ans)

exit(0)

Solution (Python):
n,k=map(int,input().split())
a=[]
b=[]
for i in range(n):
    ia,ib=map(int,input().split())
    a.append(ia)
    b.append(ib)
bit=0
while k>=(1<<bit):
    bit+=1
ret=0
for i in range(n):
    if k==k|a[i]:
        ret+=b[i]
for i in range(bit):
    if k&(1<<i):
        mask=((1<<bit)-1)^((1<<(i+1))-1)
        ok=(k&mask)|((1<<i)-1)
        tmp=0
        for j in range(n):
            if ok==ok|a[j]:
                tmp+=b[j]
        ret=max(ret,tmp)
print(ret)

Solution (Python):
N,K = map(int,input().split())
masks = [K]

bs = str(bin(K))[2:]
for i in range(len(bs) - 1):
    if bs[i] == '1':
        a = len(bs) - 1 - i
        mask = K - (1 << a)
        mask |= ((1 << a) - 1)
        masks.append(mask)

anss = [0 for i in range(len(masks))]
for i in range(N):
    a,b = map(int,input().split())
    for i,m in enumerate(masks):
        if (m | a) == m:
            anss[i] += b

print(max(anss))

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


K_2 = bin(K)[2:]
max_kouho = [K_2,("1"* (len(K_2) -1) if len(K_2)>1 else "0") ]



for i in range(1,len(K_2)-1):
    if K_2[i] == "1"  and K_2.find("0") >-1:
        max_kouho.append(
            (K_2[:i]+"0"+ ("1" * 100) )[:len(K_2)] )


AB  = [ list(map(int,input().split())) for _ in range(N)]

if K==0:
    ans =0
    for a,b in (AB):
        if a==0:
            ans +=b
    print(ans)
    exit()
dp = {key:0 for key in max_kouho}
for a,b in AB:
    
    for key in max_kouho:
        if int(key,2) |a ==int(key,2):
            dp[key]+=b
    

print(max(dp[key] for key in max_kouho ))

Solution (Python):
from collections import defaultdict


def solve():
    n, k = map(int, input().split())
    d = defaultdict(int)
    for a, b in (map(int, input().split()) for _ in range(n)):
        d[a] += b
    bk = bin(k)[2:]
    lbk = len(bk)
    e = {k: 0}
    for i, c in enumerate(bk):
        if c == '1':
            e[int(bk[:i] + '0' + '1' * (lbk - i - 1), 2)] = 0

    for a, b in d.items():
        for c in e:
            if a | c == c:
                e[c] += b
    return max(e.values())


print(solve())

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

items = list(tuple(map(int,input().split())) for _ in range(N))

l = K.bit_length()

def it():

  for i in range(l):
    if K & (1 << i):
      j = (K-(1<<i))|((1<<i)-1)
      j = ~j
      yield sum(b for a,b in items if a&j==0)
  j = ~K
  yield sum(b for a,b in items if a&j==0)

print(max(it()))

Solution (Python):

def II(): return int(input())
def ILI(): return list(map(int, input().split()))


def read():
    N, K = ILI()
    A, B = [], []
    for __ in range(N):
        a, b = ILI()
        A.append(a)
        B.append(b)
    return N, K, A, B


def solve(N, K, A, B):
    l_K = [K]
    len_bin_K = len(bin(K)) - 2
    all_1 = sum([2 ** x for x in range(len_bin_K - 1)])
    l_K.append(all_1)
    for i in range(len(bin(K)) - 4, -1, -1):
        if K >> i & 1 == 1:
            now = K >> i
            now = now & ~1
            now = ~now
            now = now << (i)
            now = ~now
            l_K.append(now)

    l_ans = [0] * len(l_K)
    for i in range(N):
        for j in range(len(l_K)):
            if l_K[j] | A[i] == l_K[j]:
                l_ans[j] += B[i]
    ans = max(l_ans)
    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()

Solution (Python):


import math
import fractions
import heapq
import collections
import re
import array
import bisect

from collections import Counter, defaultdict


def array2d(dim1, dim2, init=None):
    return [[init for _ in range(dim2)] for _ in range(dim1)]


def main():
    N, K = map(int, input().split(" "))
    ks = format(K, "b")
    masks = [K]
    for i in range(len(ks)):
        if ks[-i-1] == "1":
            nks = ks[:-i-1] + "0" + "1" * i
            masks.append(int(nks, 2))
    l = len(masks)
    vs = [0] * l
    for _ in range(N):
        a, b = map(int, input().split())
        for i in range(l):
            if a & masks[i] == a:
                vs[i] += b
    return max(vs)


if __name__ == "__main__":
    print(main())

Solution (Python):

import sys,copy,math,heapq,itertools as it,fractions,re,bisect,collections as coll

N, K = map(int, raw_input().split())
AB = [map(int, raw_input().split()) for i in xrange(N)]

b = bin(K)
bs = [K]
for i in xrange(len(b) - 1):
    nb = list(b)
    nb[i] = "0"
    nb[i + 1:] = ["1"]*len(nb[i + 1:])
    nb = int("".join(nb), 2)
    if nb <= K:
        bs.append(nb)

ans = 0
for v in bs:
    cur = 0
    for A, B in AB:
        if v|A <= v:
            cur += B
    ans = max(ans, cur)
print ans

Solution (Python):
N, K = map(int, input().split())
V = []
for i in range(N):
    a, b = map(int, input().split())
    V.append((a, b))

def solve(P):
    res = 0
    for a, b in V:
        if P & a == a:
            res += b
    return res
ans = solve(K)
for i in range(32):
    if K & (1 << i):
        P = (K | ((1 << i)-1) )^ (1 << i)
        ans = max(ans, solve(P))
print(ans)

Solution (Python):
n, k = map(int, raw_input().split())
aa = []
bb = []
for i in range(n):
    a,b = map(int, raw_input().split())
    aa.append(a)
    bb.append(b)

ans = 0

def hoge(x, k):
    xx = x
    if (x & (1 << k)) == 0:
        return x
    for i in range(k):
        x |= (1<<i)
    x -= 1 << k
    return min(xx,x)
        

for j in range(31):
    kk = hoge(k, j)
    res = 0
    for i in range(n):
        if (aa[i]|kk) == kk:
            res += bb[i]
    ans = max(ans, res)

print(ans)