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):
def main(n,k,ab):
  ks=[k]
  m=len(bin(k))-2
  
  kbin=bin(k)[2:]
  now=0
  for i in range(m):
    if kbin[i]=='1' and i<m-1:
      ks.append(now+pow(2,m-i-1)-1)
    now+=int(kbin[i])*pow(2,m-i-1)
  ans=0
  for x in ks:
    tmp=0
    for a,b in ab:
      if a|x==x:tmp+=b
    ans=max(ans,tmp)
  print(ans)

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

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

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







def solve(X):
  res = 0
  for a,b in ITEM:
    if a | X == X:
      res += b
  
  return res

wk = 1
ans = solve(K)
for i in range(1,32):
  if (K // wk) % 2 == 1:
    ans = max(ans, solve((K // (2*wk)) * 2* wk + wk-1))
  else:
    pass
  wk *= 2
  
print(ans)

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

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







def solve(X):
  res = 0
  for a,b in ITEM:
    if a | X == X:
      res += b
  
  return res

wk = 1
ans = solve(K)
for i in range(1,32):
  if (K // wk) % 2 == 1:
    ans = max(ans, solve((K // (2*wk)) * 2* wk + wk-1))
  else:
    pass
  wk *= 2
  
print(ans)

Solution (Python):
N, K = map(int,input().split())
A = [0] * N
B = [0] * N
for i in range(N):
    A[i], B[i] = map(int,input().split())

S = []
power = 2
while power <= K:
    if K & power != 0:
        S.append(K & ~power | (power - 1))
    power <<= 1
S.append(K)

ans = 0

for s in S:
    tmp = 0
    for i in range(N):
        if s & A[i] == A[i]:
            tmp += B[i]
    ans = max(ans, tmp)

print(ans)

Solution (Python):
n,k=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(n)]
ans=0
base=0
for i in range(32,-1,-1):
  if k&(2**i):
    tbase=base+2**i-1
    tmp=0
    for a,b in arr:
      if tbase==(a|tbase):
        tmp+=b
    ans=max(ans,tmp)
    base+=2**i
tmp=0
for a,b in arr:
  if base==(a|base):
    tmp+=b
ans=max(ans,tmp)
print(ans)

Solution (Python):
import math
import numpy as np
import decimal
import collections
import itertools
import sys

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = [-1 for i in range(self.n)]
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def unite(self, x, y):
        p = self.find(x)
        q = self.find(y)
        if p == q:
            return None
        if p > q:
            p, q = q, p
        self.par[p] += self.par[q]
        self.par[q] = p
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def size(self, x):
        return -self.par[self.find(x)]


def prime_numbers(x):
    if x < 2:
        return []
    prime_numbers = [i for i in range(x)]
    prime_numbers[1] = 0
    for prime_number in prime_numbers:
        if prime_number > math.sqrt(x):
            break
        if prime_number == 0:
            continue
        for composite_number in range(2 * prime_number, x, prime_number):
            prime_numbers[composite_number] = 0
    return [prime_number for prime_number in prime_numbers if prime_number != 0]
def is_prime(x):
    if x < 2:
        return False
    if x == 2 or x == 3 or x == 5:
        return True
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0:
        return False
    prime_number = 7
    difference = 4
    while prime_number <= math.sqrt(x):
        if x % prime_number == 0:
            return False
        prime_number += difference
        difference = 6 - difference
    return True

mod = 10 ** 9 + 7
class nCr():
    def __init__(self, n):
        self.n = n
        self.fa = [1] * (self.n + 1)
        self.fi = [1] * (self.n + 1)
        for i in range(1, self.n + 1):
            self.fa[i] = self.fa[i - 1] * i % mod
            self.fi[i] = pow(self.fa[i], mod - 2, mod)
    def comb(self, n, r):
        if n < r:return 0
        if n < 0 or r < 0:return 0
        return self.fa[n] * self.fi[r] % mod * self.fi[n - r] % mod

class BinaryIndexedTree():
    def __init__(self, n):
        self.n = n
        self.BIT = [0] * (self.n + 1)
    def add(self, i, x):
        while i <= self.n:
            self.BIT[i] += x
            i += i & -i
    def query(self, i):
        res = 0
        while i > 0:
            res += self.BIT[i]
            i -= i & -i
        return res

class AssociativeArray():
    def __init__(self, q):
        self.dic = dict()
        self.q = q
    def solve(self):
        for i in range(self.q):
            Query = list(map(int, input().split()))
            if Query[0] == 0:
                x, y, z = Query
                self.dic[y] = z
            else:
                x, y = Query
                if y in self.dic:
                    print(self.dic[y])
                else:
                    print(0)

def floor_sum(n, m, a, b):
    res = 0
    if a >= m:
        res += (n - 1) * n * (a // m) // 2
        a %= m
    if b >= m:
        res += n * (b // m)
        b %= m
    y_max = (a * n + b) // m
    x_max = y_max * m - b
    if y_max == 0:
        return res
    res += y_max * (n + (-x_max // a))
    res += floor_sum(y_max, a, m, (a - x_max % a) % a)
    return res

def z_algorithm(s):
    str_len = len(s)
    res = [0] * str_len
    res[str_len - 1] = str_len
    i, j = 1, 0
    while i < str_len:
        while i + j < str_len and s[i + j] == s[j]:
            j += 1
        res[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < str_len and j > res[k] + k:
            res[i + k] = res[k]
            k += 1
        i += k
        j -= k
    return res
class Manacher():
    def __init__(self, s):
        self.s = s
    def coustruct(self):
        i, j = 0, 0 
        s_len = len(s)
        res = [0] * s_len
        while i < s_len:
            while i - j >= 0 and i + j < s_len and s[i - j] == s[i + j]:
                j += 1
            res[i] = j
            k = 1
            while i - k >= 0 and k + res[i - k] < j:
                k += 1
            i += k
            j -= k
n, k = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n)]
ans = 0
for i in ab:
    if i[0] | k == k:
        ans += i[1]
cur = 0
for i in range(len(bin(k)) + 1)[::-1]:
    if k & (1 << i) > 0:
        cur += (1 << i) - 1
        cnt = 0
        for j in ab:
            if j[0] | cur <= k:
                cnt += j[1]
        ans = max(ans, cnt)
        cur += 1
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
ab=[]
for i in range(n):
	a,b=map(int,input().split())
	ab.append((a,b))
K=[k]
for i in range(1,len(bin(k)[2:])):
	r=(k-(2**i))//(2**i)*(2**i)+(2**i-1)
	K.append(r)
ans=[0]*len(K)
for x,y in ab:
	for i in range(len(K)):
		if K[i]|x==K[i]:
			ans[i]+=y
print(max(ans))

Solution (Python):
from collections import defaultdict


def main():
    N, K = map(int, input().split())
    integers = [list(map(int, input().split())) for _ in range(N)]
    
    len_bin_k = len('{:b}'.format(K))
    keys = [K]
    for shift in range(1, len_bin_k + 1):
        if (K >> shift) & 1 == 1:
            
            
            keys.append(((K >> shift) << shift) - 1)
    vals = defaultdict(int)
    for a, b in integers:
        for k in keys:
            
            if k | a == k:
                vals[k] += b
    if len(vals.values()) == 0:
        print(0)
    else:
        print(max(vals.values()))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())


N,K = MI()
K += 1
k = K.bit_length()

AB = []

for _ in range(N):
    a,b = MI()
    if a >= K:
        continue
    else:
        AB.append(([(a >> i) & 1 for i in range(k-1,-1,-1)],b))

N = len(AB)
K_bit = [(K >> i) & 1 for i in range(k-1,-1,-1)]

ANS = [0]*k  

for i in range(N):
    a,b = AB[i]
    for j in range(k):
        if K_bit[j] == 1:
            if a[j] == 0:
                ANS[j] += b
        else:
            if a[j] == 1:
                break

print(max(ANS))

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

N, K = map(int, input().split())
or_result = [K]
for i in range(K.bit_length()):
    if (1 << i) & K:
        or_result.append((K & ~((1 << i) - 1)) - 1)

values = {r:0 for r in or_result}
for _ in range(N):
    A, B = map(int, input().split())
    for key in values:
        if key & A == A:
            values[key] += B

print(max(values.values()))

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

n,k = map(int,readline().split())
ab = list(map(int,read().split()))

target = [k]
for i in range(1,30):
    if((k>>i)&1):
        target.append(( k-(1<<i)) | ((1<<i)-1) )

ans = 0
for i in target:
    val = 0
    it = iter(ab)
    for a,b in zip(it,it):
        if( a - (i&a) == 0 ):
            val += b
    ans = max(ans,val)

print(ans)

Solution (Python):
n, k = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]

ans = sum([b for a, b in ab if k & a == a])

for i in range(30):
    if k >> i & 1:
        nk = 1 << i ^ k
        for j in range(i):
            nk |= 1 << j
        ans = max(ans, sum([b for a, b in ab if nk & a == a]))
print(ans)

Solution (Python):
n,k = map(int, input().split())
ans = 0
abl = [ tuple(map(int, input().split())) for _ in range(n) ]

kset = set()
kset.add(k)
for i in range(30):
    if k&(1<<i) == 0: continue
    v = 0
    for j in range(i):
        v += pow(2,j)
    for j in range(i+1,30):
        if k&(1<<j) > 0:
            v += pow(2,j)
    kset.add(v)

kl = list(kset)
ans = 0
for ki in kl:
    v = 0
    for a,b in abl:
        if a > k: continue
        for i in range(30):
            if a&(1<<i) > 0 and ki&(1<<i) == 0:
                break
        else:
            v += b
    ans = max(ans, v)

print(ans)

Solution (Python):
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

for i in range(31):
    
    if k >> i & 1 == 0:
        continue
    nk = k
    nk &= ~(1 << i)
    for j in range(i - 1, -1, -1):
        nk |= 1 << j

    cnt = 0
    for j in range(n):
        a, b = ab[j]
        if (a & nk) == a:
            cnt += b
    ans = max(ans, cnt)
print(ans)

Solution (Python):
N,K = map(int,input().split())
X = [list(map(int,input().split())) for _ in range(N)]
K = bin(K)[2:]
K = "0"*(30-len(K))+K
A = [bin(X[i][0])[2:] for i in range(N)]
A = ["0"*(30-len(A[i]))+A[i] for i in range(N)]
F = [K]
for i in range(30):
    if K[i]=="1":
        x = K[:i]+"0"+"1"*(30-i-1)
        F.append(x)
G = []
for f in F:
    g = []
    for i in range(30):
        if f[i]=="0":
            g.append(i)
    G.append(g)
cmax = 0
for g in G:
    cnt = 0
    for i in range(N):
        a = A[i]
        flag = 0
        for j in g:
            if a[j]!="0":
                flag = 1
                break
        if flag==0:
            cnt += X[i][1]
    cmax = max(cmax,cnt)
print(cmax)

Solution (Python):
N, K = map(int,input().split())
A = []
B = []
copy = K
for i in range(N):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)
target = []
while K >= 2:
    target.append(K%2)
    K = K//2
target.append(K)

def check(A,B,N,K):
    compare = 0
    for i in range(N):
        if A[i]|K <= K:
            compare+=B[i]
    return(compare)

ans = check(A,B,N,copy)
for i in range(len(target)):
    if target[i] ==1:
        copy = copy^2**i
        if i >0:
            copy = copy | (2**i-1)
        chance = check(A,B,N,copy)
        if chance > ans:
            ans = chance
print(ans)

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

ans = 0
abl = []
for _ in range(n):
    a,b = map(int, input().split())
    abl.append((a,b))

max_bit = 0
for i in range(31):
    if k < pow(2,i):
        max_bit = i
        break

k_bits = [-1]*(max_bit)
for i in range(max_bit-1,-1,-1):
    if k&(1<<i) > 0:
        k_bits[i] = 1
    else:
        k_bits[i] = 0



k_bits = k_bits[::-1]
bits_cands = []
bits_cands.append(k_bits[::-1])
for i in range(max_bit):
    curr_row = []
    for j in range(0,i):
        curr_row.append(k_bits[j])
    if k_bits[i] == 1:
        curr_row.append(0)
        curr_row = curr_row + [1]*(max_bit-1-i)
    else:
        for j in range(i,max_bit):
            curr_row.append(k_bits[j])
    bits_cands.append(curr_row[::-1])


ans = 0
for bits in bits_cands:
    val = 0
    for a,b in abl:
        if a > k: continue
        for i in range(max_bit):
            if a&(1<<i) > 0 and bits[i] == 0:
                break
        else:
            val += b
    ans = max(ans,val)
print(ans)

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

ans=0
ab.sort()
m=bin(k)

klst=[m]
for i in range(2,len(m)):
    if m[i]=="1":
        klst.append(m[:i]+"0"+"1"*(len(m)-i-1))
for i in range(len(klst)):
    klst[i]=int(klst[i],0)

for i in klst:
    tmp=0
    for j in range(n):
        a,b=ab[j]
        if a|i==i:
            tmp+=b
    ans=max(ans,tmp)
print(ans)

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

ans=0
ab.sort()
m=bin(k)

klst=[m]
for i in range(2,len(m)):
    if m[i]=="1":
        klst.append(m[:i]+"0"+"1"*(len(m)-i-1))


for i in klst:
    tmp=0
    for j in range(n):
        a,b=ab[j]
        if a|int(i,0)==int(i,0):
            tmp+=b
    ans=max(ans,tmp)
print(ans)

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


def solve():
    N, K = map(int, input().split())
    l = [tuple(map(int, input().split())) for _ in range(N)]
    candidates = [K]
    b = 0
    for i in range(30)[::-1]:
        if K&(1<<i):
            candidates.append(b + (1<<i) - 1)
            b += (1<<i)

    ans = 0
    for k in candidates:
        buf = 0
        for i, j in l:
            if i|k==k:
                buf += j
        ans = max(ans, buf)
    print(ans)


if __name__ == "__main__":
    solve()

Solution (Python):
N, K = map(int, input().split())
l = [tuple(map(int, input().split())) for _ in range(N)]
cds = [K]
b = 0
for i in range(30)[::-1]:
    if K&(1<<i):
        cds.append(b + (1<<i) - 1)
        b += (1<<i)

ans = 0
for k in cds:
    buf = 0
    for i, j in l:
        if i|k==k:
            buf += j
    ans = max(ans, buf)
print(ans)

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


def solve():
    N, K = map(int, input().split())
    l = [tuple(map(int, input().split())) for _ in range(N)]
    candidates = [K]
    b = 0
    for i in range(30)[::-1]:
        if K&(1<<i):
            candidates.append(b + (1<<i) - 1)
            b += (1<<i)

    ans = 0
    for k in candidates:
        buf = 0
        for i, j in l:
            if i|k==k:
                buf += j
        ans = max(ans, buf)
    print(ans)


if __name__ == "__main__":
    solve()

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


def get_candidate(K):
    l = []
    b = 0
    for i in range(30)[::-1]:
        if K&(1<<i):
            l.append(b + (1<<i) - 1)
            b += (1<<i)
    return l+[K]


def get_ans(K, l):
    ans = 0
    for i, j in l:
        if i|K==K:
            ans += j
    return ans


def solve():
    N, K = map(int, input().split())
    l = [tuple(map(int, input().split())) for _ in range(N)]
    ans = 0
    for k in get_candidate(K):
        ans = max(ans, get_ans(k, l))
    print(ans)


if __name__ == "__main__":
    solve()

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


def get_candidate(K):
    l = []
    b = 0
    for i in range(30)[::-1]:
        if (K&(1<<i)):
            l.append(b + (1<<i) - 1)
            b += (1<<i)
    return l+[K]


def get_ans(K, l):
    bit = [None]*30
    for i in range(30):
        bit[i] = (K&(1<<i))>>i

    ans = 0
    for i, j in l:
        for k in range(30):
            b = (i&(1<<k))>>k
            if not ((bit[k]==1) or (b==0 and bit[k]==0)):
                break
        else:
            ans += j
    return ans


def solve():
    N, K = map(int, input().split())
    l = [tuple(map(int, input().split())) for _ in range(N)]
    ans = 0
    for k in get_candidate(K):
        ans = max(ans, get_ans(k, l))
    print(ans)


if __name__ == "__main__":
    solve()

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

def get_candidate(K):
    l = []
    b = 0
    for i in range(30)[::-1]:
        if (K&(1<<i)):
            l.append(b + (1<<i) - 1)
            b += (1<<i)
    return l+[K]

def get_ans(K):
    bit = [None]*30
    for i in range(30):
        bit[i] = (K&(1<<i))>>i

    ans = 0
    for i, j in l:
        for k in range(30):
            b = (i&(1<<k))>>k
            if not ((bit[k]==1) or (b==0 and bit[k]==0)):
                break
        else:
            ans += j
    return ans

ans = 0
for k in get_candidate(K):
    ans = max(ans, get_ans(k))
print(ans)

Solution (Python):
N, K = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
ans = sum(b for a, b in AB if a&~K==0)
for i in range(30):
    if K>>i&1:
        k = (K^1<<i)|(1<<i)-1
        ans = max(ans, sum(b for a, b in AB if a&~k==0))
print(ans)

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

M = len(bin(K))-3
ans = 0
for l in L:
    if l[0] | K == K:
        ans += l[1]
k = 0
for i in range(M, -1, -1):
    if K & (1<<i) > 0:
        k += (1<<i)-1
        temp = 0
        for l in L:
            if l[0] | k <= K:
                temp += l[1]
        ans = max(ans, temp)
        k += 1

print(ans)

Solution (Python):
n,k=map(int,input().split())
ab=[list(map(int,input(). split())) for _ in range(n)]
bk=list(bin(k)[2:])
if '0' not in bk:
  t=k
  ans=0
  for a,b in ab:
    if a<=t:ans+=b
  print(ans)
else:
  ks=[k]
  for i in range(len(bk)):
    if bk[i]=='1':
      if i==0:
        ks.append(int('1'*(len(bk)-1),2))
      else:
        ks.append(int(''.join(bk[:i])+'0'+'1'*(len(bk)-i-1),2))
  ans=[0]*len(ks)
  for a,b in ab:
    for i in range(len(ks)):
      if a&ks[i]==a:ans[i]+=b
  print(max(ans))

Solution (Python):
n,k=map(int,input().split())
ab=[list(map(int,input(). split())) for _ in range(n)]
bk=list(bin(k)[2:])
if '0' not in bk:
  t=k
  ans=0
  for a,b in ab:
    if a<=t:ans+=b
  print(ans)
else:
  ks=[k]
  for i in range(len(bk)):
    if bk[i]=='1':
      if i==0:
        ks.append(int('1'*(len(bk)-1),2))
      else:
        ks.append(int(''.join(bk[:i])+'0'+'1'*(len(bk)-i-1),2))
  ans=[0]*len(ks)
  for a,b in ab:
    for i in range(len(ks)):
      if a&ks[i]==a:ans[i]+=b
  print(max(ans))

Solution (Python):
def main():
    n, k = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(n)]
    ans = 0
    for a, b in arr:
        f = True
        for i in range(32):
            if k & (1<<i) == 0 and a & (1<<i) != 0:
                f = False
                break
        if f:
            ans += b
    for i in range(32):
        p = 1<<i
        tmp = 0
        if p & k == 0:
            continue
        for a, b in arr:
            if a <= k and a&p == 0:
                f = True
                for j in range(i+1, 32):
                    if k & (1<<j) == 0 and a & (1<<j) != 0:
                        f = False
                        break
                if f:
                    tmp += b
        if ans < tmp:
            ans = tmp
    print(ans)

if __name__ == "__main__":
    main()

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,K=MI()
    A=[0]*N
    B=[0]*N
    for i in range(N):
        a,b=MI()
        A[i]=a
        B[i]=b
        
    """
    xorだと思っていたので馬鹿みたいにむずかった...
    
    最大値の最大値，的な．
    Kを二進数表記して，bitが立っている桁を選び，i桁目とする．
    iよりも高位側はKと同じで，
    低位側を全部1にした数K2を考える．
    orがK2を超えなければOk
    """
    
    ans=0
    M=len(bin(K))-2
    
    for i in range(M):
        temp=0
        if K>>i & 1:
            K2=K-(1<<i)
            K2=K2 | ((1<<i)-1)
                    
            for k in range(N):
                if K2 | A[k] == K2:
                    temp+=B[k]  
            ans=max(ans,temp)
           
    temp=0 
    for k in range(N):
        if K | A[k] == K:
            temp+=B[k]
    ans=max(ans,temp)
    
    print(ans)
                    
                    
            
        
    
    

main()

Solution (Python):

printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7


def ddprint(x):
  if DBG:
    print(x)

n,k = inm()
if k==0:
    sm = 0
    for i in range(n):
        a,b = inm()
        if a==0:
            sm += b
    print(sm)
    exit()
pat = [k]
for i in range(29,-1,-1):
    if (k>>i)%2>0:
        pat.append((k^(1<<i))|((1<<i)-1))
vpat = [0 for x in pat]
for i in range(n):
    a,b = inm()
    for m,p in enumerate(pat):
        ok = True
        for j in range(30):
            if (p>>j)%2 < (a>>j)%2:
                ok = False
                break
        if ok:
            vpat[m] += b
print(max(vpat))

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 = map(int, input().split())
a = [None]*n
b = [None]*n
for i in range(n):
    a[i],b[i] = map(int, input().split())

l = k.bit_length()
def sub(k):
    ans = 0
    for num,val in zip(a,b):
        if (k|num) == k:
            ans += val
    return ans
ans = sub(k)
for i in range(l):
    
    if k>>i&1:
        kk = ((k>>i)-1)*(1<<i) + (1<<i) - 1
        val = sub(kk)
        ans = max(ans, val)

print(ans)

Solution (Python):
n,k = map(int,input().split())
l = [list(map(int,input().split())) for i in range(n)]
l.sort()
s = bin(k)[2:]
s = s[::-1]
m = len(s)
dp = [0]*(m+1)

for i,v in l:
    if i > k:
        break
    check = True
    for j in range(m-1,-1,-1):
        
        if ((i>>j)&1) and s[j] == "0":
            check = False
            break
        if s[j] == "0":
            continue
        if s[j] == "1" and (not (i>>j)&1):
            dp[j] += v
    if check:
        dp[-1] += v
    
print(max(dp))

Solution (Python):
import sys

input=sys.stdin.readline

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

bit=[]
for i in range(0,30):
    if K>>i &1==1:
        bit.append(i)

ans=0
for j in range(N):
    a,b=integer[j]
    if a|K==K:
        ans+=b

for i in bit:
    check=(K>>i)-1
    test=0
    for j in range(N):
        a,b=integer[j]
        if a>>i|check==check:
            test+=b
    ans=max(ans,test)

print(ans)

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

def calc(x):
    res = 0
    
    for A, B in AB:
        if A|x==x:
            res += B
    
    return res

N, K = map(int, input().split())
S = format(K, 'b')
AB = [tuple(map(int, input().split())) for _ in range(N)]
ans = calc(K)
now = 0

for i in range(len(S)):
    if S[i]=='1':
        bit = len(S)-i-1
        ans = max(ans, calc(now+2**bit-1))
        now += 2**bit

print(ans)

Solution (Python):
N,K = list(map(int,input().split()))
AB = [list(map(int,input().split())) for i in range(N)]
bitK = bin(K)[2:]
bitK = bitK[::-1]
ans = 0
for i in range(N):
    if AB[i][0]|K==K:
        ans += AB[i][1]

for i in range(len(bitK)):
    score = 0
    if bitK[i]=="1":
        check = (K >> i)-1
        for j in range(N):
            if AB[j][0]>>i|check == check:
                score+=AB[j][1]
    ans = max(score,ans)

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)]
i = 0
ans = 0
for A, B in AB:
    if (A | K) == K:
        ans += B
while (1 << i) <= K:
    if K >> i & 1:
        tmp = 0
        for A, B in AB:
            if A >> i & 1:
                continue
            if ((A | K) >> (i+1)) == (K >> (i+1)):
                tmp += B
        ans = max(ans, tmp)
    i += 1
print(ans)

Solution (Python):
N,K,*X = map(int,open(0).read().split())
S = bin(K)[2:]
L = len(S)
ls = [(a,b) for a,b in zip(*[iter(X)]*2)]
s = '0'
ans = 0
for i,c in enumerate(S):
  if c=='0':
    s += c
    continue
  j = L-i
  m = (1<<(j-1))-1
  n = int(s,2)<<j
  x = m|n
  v = 0
  for a,b in ls:
    if x==x|a:
      v += b
  ans = max(v,ans)
  s += c
v = 0
for a,b in ls:
  if K==K|a:
    v += b
ans = max(ans,v)
print(ans)

Solution (Python):
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

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


def main():
	N, K = getlist()
	numL = []
	for i in range(N):
		A, B = getlist()
		numL.append([A, B])
	KK = K

	Kbit = []
	while True:
		Kbit.append(K % 2)
		K = int(K // 2)
		if K == 0:
			break

	Kbit = Kbit[::-1]
	M = len(Kbit)
	Ksum = [0] * M
	if Kbit[0] == 1:
		Ksum[0] = 2 ** (M - 1)
	for i in range(1, M):
		if Kbit[i] == 1:
			Ksum[i] = Ksum[i - 1] + 2 ** (M - 1 - i)
		else:
			Ksum[i] = Ksum[i - 1]

	
	

	ans = 0
	for i in range(1, M - 1):
		if Kbit[i] == 1:
			var = Ksum[i - 1] + 2 ** (M - 1 - i) - 1
			cnt = 0
			for j in range(N):
				A = numL[j][0]
				B = numL[j][1]
				if var | A == var:
					cnt += B

			ans = max(ans , cnt)

	cnt = 0
	for i in range(N):
		A = numL[i][0]
		B = numL[i][1]
		if (2 ** (M - 1) - 1) | A == (2 ** (M - 1) - 1):
			cnt += B
	ans = max(ans, cnt)
	cnt = 0
	for i in range(N):
		A = numL[i][0]
		B = numL[i][1]
		if KK | A == KK:
			cnt += B
	ans = max(ans, cnt)

	print(ans)

if __name__ == '__main__':
	main()

Solution (Python):
INF = 10 ** 15
MOD = 10 ** 9 + 7 
from collections import deque

def main():
    N,K = map(int,input().split())
    number = [tuple(map(int,input().split())) for _ in range(N)]
    if K == 0:
        ans = 0
        for a,b in number:
            if a == 0:
                ans += b
        print(ans)
        return 

    msb = 30
    while (K>>msb)&1 == 0:
        msb -= 1

    ans = 0
    for i in range(msb + 1):
        x = K >> i
        if i > 0:
            x -= 1
        ret = 0
        for a,b in number:
            if (a>>i) | x == x:
                ret += b
        ans = max(ans,ret)      
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
import sys

input=sys.stdin.readline

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

bit=[]
for i in range(0,30):
    if K>>i &1==1:
        bit.append(i)

ans=0
for j in range(N):
    a,b=integer[j]
    if a|K==K:
        ans+=b

for i in bit:
    check=(K>>i)-1
    test=0
    for j in range(N):
        a,b=integer[j]
        if a>>i|check==check:
            test+=b
    ans=max(ans,test)

print(ans)

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

def solve(k):
  res = 0
  for a, b in AB:
    if a | k <= k:
      res += b
  return res

ans = solve(K)
while K:
  bottom1 = K & -K
  k = (K ^ bottom1) + (bottom1 - 1)
  ans = max(ans, solve(k))
  K ^= bottom1

print(ans)

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))






N,K = LI()
A0,B0 = LIR(N,2)

A = []
B = []
for i in range(N):
    if A0[i] <= K:
        A.append(A0[i])
        B.append(B0[i])

Ks = format(K,'b')
L = len(Ks)
last_zero = -1
for i in range(L)[::-1]:
    if Ks[i] == '0':
        last_zero = i
        break

if last_zero == -1:
    print(sum(B))
else:
    zeros = []
    must_zero = []
    for i,s in enumerate(Ks):
        if s == '1':
            must_zero.append(zeros+[i])
        else:
            zeros.append(i)
            if i == last_zero:
                must_zero.append(zeros)
                break
    ans = 0
    for zl in must_zero:
        temp = 0
        for a,b in zip(A,B):
            flag = False
            for i in zl:
                if a & 1<<(L-i-1) != 0:
                    flag = True
                    break
            if not flag:
                temp += b
        if temp > ans:
            ans = temp
    print(ans)