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):
import sys
input = sys.stdin.readline

n, k = map(int,input().split())
A = [list(map(int,input().split())) for i in range(n)]
l = 32
bk = format(k, "b").zfill(l)
B = [k]
nk = 0
for i in range(l):
    if bk[i] == "1":
        nk += 2**(l-1-i)
        B.append(nk - 1)




ans0 = 0
for i in range(len(B)):
    ans = 0
    for j in range(n):
        if B[i] | A[j][0] == B[i]:
            ans += A[j][1]
    ans0 = max(ans0, ans)
print(ans0)

Solution (Python):
N,K,*X = map(int, open(0).read().split())
S = bin(K)[2:]
L = len(S)
one = set()
ls = [(a,b) for a,b in zip(*[iter(X)]*2) if a<=K]
kls = [K]
ans = 0
for i in range(L):
  if S[i]=='1':
    m = int(S[:i]+'0'+'1'*(L-i-1),2)
    kls.append(m)
for k in kls:
  m = 0
  for a,b in ls:
    if k==k|a:
      m += b
  ans = max(ans,m)
print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7



n, k = LI()
AB = LIR(n)

def count(d):
    ret = 0
    for a, b in AB:
        if not ~d & a:
            ret += b
    return ret

ans = count(k)
for i in range(k.bit_length()):
    if k >> i & 1:
        ans = max(ans, count(((k >> i) << i) - 1))

print(ans)

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


bit = []
for a, b in AB:
    tmp = set()
    for i in range(31):
        if a & 1:
            tmp.add(i)
        a //= 2
    bit.append((tmp, b))

def cost(S):
    res = 0
    for T, b in bit:
        if S.issuperset(T):
            res += b
    return res


Kbit = set()
Ktmp = K
for i in range(31):
    if Ktmp & 1:
        Kbit.add(i)
    Ktmp //= 2

ans = cost(Kbit)
for i in Kbit:
    T = Kbit.copy()
    T -= {i}            
    T |= set(range(i))  
    ans = max(ans, cost(T))

print(ans)

Solution (Python):
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
AB = np.array([lr() for _ in range(N)], dtype=np.int64)
A = AB[:, 0]
B = AB[:, 1]
answer = 0

def F(x):
    global answer
    
    index = np.where((A|x) <= x)[0]
    if index is not None:
        if np.sum(B[index]) > answer:
            answer = B[index].sum()

cur = 0
F(K)
for i in range(K.bit_length()-1, -1, -1):
    if (((1 << i) & K) >> i) & 1:
        F(cur + ((1<<i) - 1))
        cur += (1<<i)

print(answer)

Solution (Python):
n,k=map(int,input().split())
s=[list(map(int,input().split()))for i in range(n)]
p=0
for i in range(31):
    c=1
    if i!=0:
        if k|(2**i)==k:
            k-=2**i
            k=k|(2**i-1)
        else:
            c=0
    if c:
        q=0
        for j,h in s:
            if k|j==k:
                q+=h
        p=max(p,q)
print(p)

Solution (Python):
n,k=map(int,input().split())
l=[]
for i in range(n):
    l.append(list(map(int,input().split())))
ans=0
for i in range(n):
    if k|l[i][0]==k:
        ans+=l[i][1]
t=0
for i in range(30):
    if (1<<29-i)&k:
        t+=2**(29-i)
        p=t-1
        kai=0
        for i in range(n):
            if p|l[i][0]==p:
                kai+=l[i][1]
        ans=max(ans,kai)
print(ans)

Solution (Python):
N,K=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N)]
dp=[0]*31
for a,b in AB:
    x=1
    for i in range(30):
        if K&x and ((K-x)|(x-1))&a==a:
            dp[i]+=b
        x<<=1
    if K&a==a:
        dp[-1]+=b
print(max(dp))

Solution (Python):

n,k = map(int,input().split())
judge = [k]
for d in range(30):
  kx = k // 2**d * 2**d
  if kx != 0:
    judge.append(kx)
  else:
    break
l = len(judge)
for i in range(1,l):
  judge[i] -= 1
judge.reverse()

can = [0 for _ in range(l)]
for _ in range(n):
  a,b = map(int,input().split())
  for i in range(l):
    if a | judge[i] == judge[i]:
      
      can[i] += b
  

print(max(can))

Solution (Python):
n, k = map(int, input().split())
a, b = [0] * n, [0] * n
for i in range(n):
    a[i], b[i] = map(int, input().split())
ans = 0
z = list(zip(a, b))
for x, y in z:
    if (k | x) == k:
        ans += y
for i in range(30):
    if (k >> i) & 1:
        res = 0
        t = ((k >> (i + 1)) << (i + 1)) + (1 << i) - 1
        for x, y in z:
            if (t | x) == t:
                res += y
        ans = max(ans, res)
print(ans)

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,K=MI()
    K_bin = bin(K)[2:]
    AB=LLIN(N)

    ans = 0
    for a,b in AB:
        if a&K==a:
            ans += b

    for i in range(len(K_bin)):
        if K_bin[i]=="0":
            continue
        i_inv = len(K_bin)-(i+1)
        res = 0
        k = K - (1<<i_inv)
        for a,b in AB:
            left_a = (a>>i_inv<<i_inv) 
            if left_a&k==left_a:
                res += b
            else:
                continue
        ans = max(ans, res)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,K=MI()
    K_bin = bin(K)[2:]
    AB=LLIN(N)

    ans = 0
    for a,b in AB:
        if a&K==a:
            ans += b

    for i in range(len(K_bin)):
        if K_bin[i]=="0":
            continue
        i_inv = len(K_bin)-(i+1)
        res = 0
        
        
        k = K - (1<<i_inv)
        for a,b in AB:
            left_a = (a>>i_inv<<i_inv) 
            
            if left_a&k==left_a:
                res += b
            else:
                continue
        ans = max(ans, res)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N, K = (int(i) for i in input().split())
    AB = [[int(i) for i in input().split()] for j in range(N)]
    K_bi = str(bin(K))[2:]
    M = len(K_bi)
    posi = []
    for i in range(M-1):
        if K_bi[i] == "1":
            posi.append(i)
    ans = 0
    for i in posi:
        cur_bit = int(K_bi[:i] + "0" + "1" * (M - (i + 1)), 2)
        cur_s = 0
        for a, b in AB:
            if a | cur_bit == cur_bit:
                cur_s += b
        ans = max(ans, cur_s)
    cur_s = 0
    for a, b in AB:
        if a | K == K:
            cur_s += b
    ans = max(ans, cur_s)
    print(ans)


if __name__ == '__main__':
    main()

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

n, k = map(int, input().split())
m = map(int, read().split())
AB = list(zip(m, m))
k_bin = bin(k)[2:]
l = len(k_bin)
def count(d):
  s = 0
  for a, b in AB:
    if a & ~d:
      continue
    s += b
  return s

ans = count(k)
for i in range(l):
  if (k >> i) & 1:
    d = ((k >> i) << i) - 1
    temp = count(d)
    ans = max(ans, temp)
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
a = [list(map(int,input().split())) for i in range(n)]
ans = [0]
l = max(k.bit_length(),1)
for i in range(l-1,-1,-1):
  if i == 0:
    x = k
  elif k & 1 << i:
    x = (k >> (i+1)) << i+1 | (1 << i)-1
  sm = 0
  for j in range(n):
    if a[j][0] | x == x:
      sm += a[j][1]
  ans.append(sm)
print(max(ans))

Solution (Python):
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
a = []
for _ in range(N):
  u, v = map(int, input().split())
  a.append((u, v))
b = bin(K)[2: ]
t = [K]
for i in range(len(b)):
  if b[i] == "1":
    tt = 0
    for j in range(i):
      if b[j] == "1": tt += 1 << (len(b) - j - 1)
    for j in range(i + 1, len(b)):
      tt += 1 << (len(b) - j - 1)
    t.append(tt)
res = 0
for tt in t:
  ttt = 0
  for i in range(N):
    u, v = a[i]
    if tt & u == u:
      ttt += v
  res = max(res, ttt)
print(res)

Solution (Python):
def examD():
    N, K = LI()
    A = [0]*N; B = [0]*N
    for i in range(N):
        A[i],B[i] = LI()
    ans = 0; bi = 32
    for i in range(bi+1):
        if K&(1<<(bi-i))==0:
            if i!=bi:
                continue
        mask = 2**(bi-i)
        for j in range(i):
            if K&(1<<(bi-j))==0:
                mask += 2**(bi-j)

        now = 0
        for i in range(N):
            if A[i]&mask>0:
                continue

            now +=B[i]
        ans = max(ans,now)

    mask = K^(2**bi -1)
    now = 0
    for i in range(N):
        if A[i] & mask > 0:
            continue
        
        now += B[i]
    ans = max(ans, now)
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, AB):
    ans = 0
    for i in range(K.bit_length()-1, -2, -1):
        mask = K
        if i > -1:
            if mask & 1 << i:
                mask -= 1 << i
            else:
                continue
        for j in range(i):
            mask |= 1 << j
        cand = 0
        v = 0
        for a, b in AB:
            if (a | mask) == mask:
                cand += b
                v |= a
        assert v <= K
        ans = max(ans, cand)
    return ans



def main():
    N, K = read_int_n()
    AB = [read_int_n() for _ in range(N)]
    print(slv(N, K, AB))


if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter

N, K, *AB = map(int, open(0).read().split())

C = Counter()
for a, b in zip(*[iter(AB)] * 2):
    C[a] += b

ma = sum(v for k, v in C.items() if k | K == K)

S = list(bin(K)[2:])
i = -1
for _ in range(S.count('1')):
    T = S[:]
    i = T.index('1', i + 1)
    T[i:] = "0" + "1" * (len(T) - i - 1)

    T = int("".join(T), 2)
    ma = max(ma, sum(v for k, v in C.items() if k | T == T))

print(ma)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10


def solve():
    n, k = LI()
    ab = LIR(n)
    def f(k):
        res = 0
        for a, b in ab:
            if k & a == a:
                res += b
        return res
    ans = f(k)
    for i in range(31):
        i1 = (1 << i)
        if k & i1:
            K = (k | (i1 - 1)) ^ i1
            res = f(K)
            if ans < res:
                ans = res
    print(ans)
    return



if __name__ == '__main__':
    solve()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10


def solve():
    n, k = LI()
    ab = LIR(n)
    ans = 0
    for a, b in ab:
        if k & a == a:
            ans += b
    for i in range(31):
        if k & (1 << i):
            res = 0
            K = (k | ((1 << i) - 1)) ^ (1 << i)
            for a, b in ab:
                if K & a == a:
                    res += b
            if ans < res:
                ans = res
    print(ans)
    return



if __name__ == '__main__':
    solve()

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

bs = {K: 0}
x = K
while x:
    bs[x - 1] = 0  
    x -= x & (-x)  
    

for _ in range(N):
    num, value = map(int, input().split())
    for b in bs:
        if (b | num) == b:  
            bs[b] += value

print(max(bs.values()))

Solution (Python):



N, K = map(int, input().split())

bs = {K: 0}
for j in range(K.bit_length()):
    if K & (1 << j) > 0:
        bs[K & ~(1 << j) | ((1 << j) - 1)] = 0
        

for _ in range(N):
    num, value = map(int, input().split())
    for b in bs:
        if (b | num) == b:
            bs[b] += value

print(max(bs.values()))

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

AB = []

for i in range(N):

    a,b = map(int,input().split())
    AB.append([a,b,format(a,'b')])

kb = format(K,'b')

ans = 0

for i in range(len(kb)):

    now = 0
    if kb[-1-i] == "1":

        for j in range(N):

            flag = True
            at = AB[j][2]

            if len(kb) < len(at):
                continue

            for m in range(len(at)):

                

                if m == i and at[-1-m] == "1":
                    flag = False
                    break

                elif m > i and kb[-1-m] == "0" and at[-1-m] == "1":
                    flag = False
                    break

            if flag:
                now += AB[j][1]

        
        ans = max(ans,now)
        
print (ans)

Solution (Python):
import copy
N,K=map(int,input().split())
L=[]
for i in range(N):
    a,b=map(int,input().split())
    if a<=K:
        L.append([a,b])


k=[]
num=copy.deepcopy(K)
for i in range(30):
    if num//(2**(29-i))==1:
        k.append(1)
        num%=(2**(29-i))
    else:
        k.append(0)
        num%=(2**(29-i))
        
ans=0
for a,b in L:
    if K|a==K:
        ans+=b
NUM=0
for i in range(30):
    if k[i]==1:
        cnt=0
        NUM+=2**(29-i)
        for a,b in L:
            if K-2**(29-i)|a<NUM:
                cnt+=b
        if ans<cnt:
            ans=cnt
        
    
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,k=map(int,input().split())
    k+=1
    AB=[tuple(map(int,input().split())) for _ in range(n)]

    dp=[0]*35 
    
    
    for a,b in AB:
        for d in range(34,-1,-1):
            kd=(k>>d)&1
            ad=(a>>d)&1
            if(ad>kd): break
            if(ad<kd):
                dp[d]=dp[d]+b

    print(max(dp))
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,k=map(int,input().split())
    k+=1
    AB=[tuple(map(int,input().split())) for _ in range(n)]

    dp=[0]*35 
    
    
    for a,b in AB:
        ndp=dp[:]
        for d in range(34,-1,-1):
            kd=(k>>d)&1
            ad=(a>>d)&1
            if(ad>kd): break
            if(ad<kd):
                ndp[d]=dp[d]+b
        dp=ndp

    print(max(dp))
resolve()

Solution (Python):
def main():
    m=30
    n,k=map(int,input().split())
    ab=[list(map(int,input().split())) for _ in [0]*n]
    test=[k]
    k=(("0"*m)+(bin(k)[2:]))[-m:]
    for i in range(m):
        if k[i]=="1":
            test.append(int(k[:i]+"0"+"1"*(m-i-1),2))
    m=0
    for t in test:
        cnt=0
        for a,b in ab:
            if a|t==t:
                cnt+=b
        m=max(cnt,m)
    print(m)
main()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,k = LI()
    s = defaultdict(lambda : 0)
    v = []
    for i in range(n):
        a,b = LI()
        s[a] += b
        v.append((a,b))
    v.sort()
    f = [0]*31
    i = 0
    j = 1
    su = 0
    for a,b in v:
        if a > j:
            f[i] = su
            i += 1
            j <<= 1
            j += 1
        su += b
    f[i] = su
    for j in range(i,30):
        f[j+1] = f[j]
    f.insert(0,0)
    l = []
    for i in range(31):
        if k&(1<<i):
            l.append(i)
    l = l[::-1]
    ans = s[0]
    p = 0
    for i in l:
        p |= (1<<i)-1
        res = 0
        for a,b in v:
            if a&p == a:
                res += b
        if ans < res:
            ans = res
        p += 1
        res = 0
        for a,b in v:
            if a&p == a:
                res += b
        if ans < res:
            ans = res
    print(ans)
    return



if __name__ == "__main__":
    solve()

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

ret = 0
for A, B in AB :
    if A & ~K == 0 :
        ret += B
        
for i in range(30) :
    if K & (1 << i) == 0 :
        continue
        
    k = K
    k ^= 1 << i
    k |= (1 << i) - 1
    s = 0
    for A, B in AB :
        if A & ~k == 0 :
            s += B
            
    ret = max(ret, s)
    
print(ret)

Solution (Python):
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = list(map(int, sys.stdin.readline().split()))
A, B = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N)]))

A = np.array(A, dtype=int)
B = np.array(B, dtype=int)

ans = B[np.bitwise_or(A, K) == K].sum()
for i in range(1, K.bit_length() + 1):
    if K >> i & 1:
        k = (K - (1 << i)) | ((1 << i) - 1)
        
        
        ans = max(ans, B[np.bitwise_or(A, k) == k].sum())
print(ans)

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

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

L = len(bin(K))-2

ans = 0
for a, b in AB:
    if (K | a) == K:
        ans += b

for n in reversed(range(L)):
    if (1 << n) & K:
        score = 0
        mask = (((1<<L)-(1<<n)) & K) - 1
        for a, b in AB:
            if (mask | a) == mask:
                score += b
        ans = max(ans, score)
print(ans)

Solution (Python):
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools

import queue
from collections import deque



def main():
    num, k = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(num)]

    ans_dic = defaultdict()
    ans_dic[k] = 0

    bin_data = list(bin(k)[2:])
    for i in range(len(bin_data)):
        if bin_data[i] == '1':
            new_data = bin_data[:i] + ['0'] + ['1' for j in range(len(bin_data) - i - 1)]
            now_str = ''.join(new_data)
            now_int = int(now_str, 2)
            ans_dic[now_int] = 0

    


    for i in range(num):
        a, b = data[i]
        for key in ans_dic.keys():
            if key | a == key:
                ans_dic[key] += b

    ans = max(list(ans_dic.values()))
    print(ans)




if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
a = []
b = []
for _ in [0]*n:
    A,B = map(int,input().split())
    a.append(A)
    b.append(B)

judgeNum = pow(2,30)-1

res = 0
for i in range(29,-1,-1):
    tmp = 0
    if (k>>i)&1 == 0:
        judgeNum -= (1<<i)
    else:
        tmpJudge = judgeNum - (1<<i)
        for e,v in zip(a,b):
            if tmpJudge | e == tmpJudge:
                tmp += v
        res = max(res,tmp)
tmp = 0
for e,v in zip(a,b):
    if k | e == k:
        tmp += v
res = max(res,tmp)

print(res)

Solution (Python):
N, K= map(int, input().split())
A = []
B = []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
ans = 0
for i in range(30):
    res = 0
    k = K>>i
    if k & 1:
        for a, b in zip(A, B):
            if not (a>>i) & 1 and ((a>>i)| k)<=k:
                res+=b
    ans = max(res, ans)
res = 0
for a, b in zip(A, B):
    if a | K <= K:
        res+=b
ans = max(ans, res)
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))


def main():
    n, k = map(int, input().split())
    ab = [tuple(map(int, input().split())) for _ in range(n)]
    ans = 0
    for a, b in ab:
        if k | a == k:
            ans += b
    
    for j in range(30):
        if (k>>j)&1:
            k ^= (1<<j)
            tmp = 0
            for a, b in ab:
                if k | a == k:
                    tmp += b
            ans = max(ans, tmp)
        k ^= (1<<j)
    
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import*
d=defaultdict(int)
n,k,*t=map(int,open(0).read().split())
for a,b in zip(*[iter(t)]*2):d[a]+=b
d=d.items()
m=sum(y for x,y in d if k|x==k)
*k,=bin(k)[2:]
i=-1
for _ in range(k.count('1')):
  t=k[:]
  i=t.index('1',i+1)
  t[i]='0'
  for j in range(i+1,len(t)):t[j]='1'
  t=int(''.join(t),2)
  m=max(m,sum(y for x,y in d if t|x==t))
print(m)

Solution (Python):
from collections import*
d=defaultdict(int)
n,k,*t=map(int,open(0).read().split())
for a,b in zip(*[iter(t)]*2):d[a]+=b
d=d.items()
m=sum(y for x,y in d if k|x==k)
*k,=bin(k)[2:]
i=-1
for _ in range(k.count('1')):
  t=k[:]
  i=t.index('1',i+1)
  t[i]='0'
  for j in range(i+1,len(t)):t[j]='1'
  t=int(''.join(t),2)
  m=max(m,sum(y for x,y in d if t|x==t))
print(m)

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

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




def isOk(k, n):
    maskK = (K >> k)
    maskN = (n >> k)

    if maskN % 2 == 1:
        return False

    if (maskK | maskN) == maskK:
        return True
    else:
        return False

ans = sum([a for n, a in numbers if (n | K) == K])
for k in range(30):
    if K & (1 << k):
        s = 0
        add = []
        for n, a in numbers:
            if isOk(k, n):
                s += a
                add.append(a)
        ans = max(ans, s)

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))


def main():
    n, k = map(int, input().split())
    ab = [tuple(map(int, input().split())) for _ in range(n)]
    ans = 0
    
    for a, b in ab:
        if k&a == a:
            ans += b
    
    i = 1
    while i<=k:
        
        if k&i:
            k ^= i
            tmp = 0
            for a, b in ab:
                if k&a == a:
                    tmp += b
            if ans < tmp:
                ans = tmp
        k ^= i
        i *= 2
    
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n, k = [int(item) for item in input().split()]
ab = []
for i in range(n):
    a, b = [int(item) for item in input().split()]
    ab.append((a, b))
ab.sort(reverse=True)

candidate = [k]
for i in range(32):
    cand = 0
    if k & 1 << i:
        for j in range(i):
            cand += 1 << j
        for j in range(i + 1, 32):
            if k & 1 << j:
                cand += 1 << j
        candidate.append(cand)

ans = 0
for cand in candidate:
    ret = 0
    for a, b in ab:
        if cand | a == cand:
            ret += b
    ans = max(ans, ret)
print(ans)

Solution (Python):
import bisect
N, K = [int(_) for _ in input().split()]
AB = sorted([[int(_) for _ in input().split()] for _ in range(N)])
b = [int(_) for _ in bin(K)[-1:1:-1]]
cand = [0]

ans = 0
for ab in AB:
    if ab[0] & ~K:
        continue
    ans += ab[1]

for p in range(K.bit_length()):
    q = K >> p
    if q & 1:
        r = (q << p) - 1
        now = 0
        for ab in AB:
            if ab[0] & ~r:
                continue
            now += ab[1]
        ans = max(ans, now)
print(ans)

Solution (Python):
N, K = map(int, input().split())
A = [[0 for _ in range(N)] for _ in range(30)]
B = [0] * N
for i in range(N):
  a, b = map(int, input().split())
  for j in range(30):
    A[j][i] = a % 2
    a //= 2
  B[i] = b
M = [0] * 30
_M = [0] * N
_K = K
for i in range(30):
  k = _K % 2
  M[i] = k
  _K //= 2
  if k:
    continue
  for j in range(N):
    _M[j] += A[i][j]
cnt = 0
for i in range(N):
  if _M[i]:
    continue
  cnt += B[i]
Z = [0] * N
for i in range(30):
  if M[i] == 0:
    for j in range(N):
      Z[j] += A[i][j]
  else:
    _cnt = 0
    for j in range(N):
      _M[j] += A[i][j] - Z[j]
      Z[j] = A[i][j]
      if _M[j]:
        continue
      _cnt += B[j]
    cnt = max(_cnt, cnt)
print(cnt)

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)