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
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    N, K = NMI()
    integars = [NLI() for _ in range(N)]

    Kr = [K]
    now_k = 0
    for i in range(32, -1, -1):
        now_bit = (K >> i) & 1
        if now_bit == 0:
            continue
        now_k += pow(2, i)
        Kr.append(now_k - 1)
    ans = 0
    for kr in Kr:
        tmp = 0
        for a, b in integars:
            if (kr | a) == kr:
                tmp += b
        ans = max(ans, tmp)
    print(ans)



if __name__ == "__main__":
    main()

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

k_subset = [k]
for i in range(len(bin(k)) - 2):
    if (k >> i) & 1:
        x = k & ~(1 << i)  
        x = x | ((1 << i) - 1)  
        k_subset.append(x)

ans = max(sum(b for a, b in ab if a | x == x) for x in k_subset)

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 == k)
k_bin = bin(k)

for i in range(len(k_bin) - 2):
    if (k >> i) & 1:
        x = k_bin[:-(i + 1)] + '0' + '1' * i
        x = int(x, 0)

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

print(ans)

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

def main():
    n,k=map(int,readline().split())
    ab=[list(map(int,l.split())) for l in read().splitlines()]
    
    ek=0
    while k>>ek:
        ek+=1
    ans=0
    for i in range(ek):
        if k>>i&1:
            m=(k>>(i+1))<<(i+1)|((1<<i)-1)
            ans=max(ans,sum((e[1] for e in ab if e[0]|m==m)))
    ans=max(ans,sum((e[1] for e in ab if e[0]|k==k)))
    print(ans)

if __name__=='__main__':
    main()

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

def main():
    n,k=map(int,readline().split())
    ab=[list(map(int,l.split())) for l in read().splitlines()]
    
    ek=0
    while k>>ek:
        ek+=1
    ans=0
    for i in range(ek):
        if k>>i&1:
            m=(k>>(i+1))<<(i+1)|((1<<i)-1)
            ans=max(ans,sum(e[1] for e in ab if e[0]|m==m))
    ans=max(ans,sum(e[1] for e in ab if e[0]|k==k))
    print(ans)

if __name__=='__main__':
    main()

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

def main():
    n,k=map(int,readline().split())
    ab=[list(map(int,l.split())) for l in read().splitlines()]
    
    ek=0
    while k>>ek:
        ek+=1
    ans=0
    for i in range(ek):
        if k>>i&1:
            m=(k>>(i+1))<<(i+1)|((1<<i)-1)
            ans=max(ans,sum([e[1] for e in ab if e[0]|m==m]))
    ans=max(ans,sum([e[1] for e in ab if e[0]|k==k]))
    print(ans)

if __name__=='__main__':
    main()

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

def main():
    n,k=map(int,readline().split())
    ab=[list(map(int,l.split())) for l in read().splitlines()]
    
    ek=0
    while k>>ek:
        ek+=1

    cand=[]
    for i in range(ek):
        if k>>i&1:
            m=(k>>(i+1))<<(i+1)|((1<<i)-1)
            cand.append(sum([e[1] for e in ab if e[0]|m==m]))
    cand.append(sum([e[1] for e in ab if e[0]|k==k]))
    print(max(cand))

if __name__=='__main__':
    main()

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

Kbit=[0]*30
K2=K
for i in range(30):
  if K2%2==1:
    Kbit[-1-i]=1
  K2//=2


alist=[]
blist=[]
for _ in range(N):
  A,B=map(int,input().split())
  alist.append(A)
  blist.append(B)
  
answer=0
for i in range(N):
  if K|alist[i]==K:
    answer+=blist[i]


for j in range(30):
  if Kbit[j]==1:
    K2bit=Kbit[:]
    K2bit[j]=0
    for k in range(j+1,30):
      K2bit[k]=1
    K2=0
    for k in range(30):
      K2<<=1
      K2+=K2bit[k]
    
      
    neq_ans=0
    for i in range(N):
      if K2|alist[i]==K2:
        neq_ans+=blist[i]
    
    answer=max(answer,neq_ans)
    
print(answer)

Solution (Python):


import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union































def main():
    Num = Union[int, float]
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input():  return sys.stdin.readline().rstrip()
    def ii():     return int(input())
    def isp():    return input().split()
    def mi():     return map(int, input().split())
    def mi_0():   return map(lambda x: int(x)-1, input().split())
    def lmi():    return list(map(int, input().split()))
    def lmi_0():  return list(map(lambda x: int(x)-1, input().split()))
    def li():     return list(input())
    def debug(x): print(x, file=sys.stderr)
    


    def pattern_to_int(pattern):
        size = len(pattern)
        num = 0
        for i in range(size):
            if pattern[i]:
                num += (1 << i)
        return num


    def calc_max_value(pattern_int):
        total = 0
        for num, value in L:
            if (pattern_int | num) == pattern_int:
                total += value
        return total


    def solve(pattern):
        pattern_int = pattern_to_int(pattern)
        
        return calc_max_value(pattern_int)

    
    
    n, k = mi()
    L = [lmi() for _ in range(n)]

    ans = -1
    d = k.bit_length()

    b = [0] * 30
    flag = []
    for i in range(d):
        if k & (1 << i):
            b[i] = 1
            flag.append(i)
    
    

    for i in flag:
        pattern = b[:]
        
        pattern[i] = 0
        for low in range(i):
            pattern[low] = 1
        ans = max(ans, solve(pattern))
    
    ans = max(ans, solve(b))
    print(ans)

    


if __name__ == "__main__":
    main()

Solution (Python):

N, K = map(int, input().split())
S = format(K, "0%ib" % 30)

d = []
use = []
for i in range(N):
    x, y = map(int, input().split())
    d.append((x, y))
for i in range(30):
    if S[i] == "1":
        que = S[:i] + "0" + "1"*(29-i)
        use.append(int(que, 2))

use.append(int(S, 2))
use = set(use)
ans = 0

for some in use:
    s=0
    for num, value in d:
        if num|some == some:
            s += value
    ans = max(s, ans)
print(ans)

Solution (Python):

N, K = map(int, input().split())
S = format(K, "0%ib" % 30)

d = []
use = []
for i in range(N):
    x, y = map(int, input().split())
    d.append((x, y))
for i in range(30):
    if S[i] == "1":
        que = S[:i] + "0" + "1"*(29-i)
        use.append(int(que, 2))

use.append(int(S, 2))
use = set(use)
ans = 0

for some in use:
    s=0
    for num, value in d:
        if num|some == some:
            s += value
    ans = max(s, ans)
print(ans)

Solution (Python):
import copy
import sys
input = sys.stdin.readline
n,k = map(int, input().split())
data = []
bit_k = format(k, 'b')
len_k = len(bit_k)
for i in range(n):
    a, b = map(int, input().split())
    if a <= k:
        tmp = format(a, 'b')
        tmp = tmp.zfill(len_k)
        data.append([tmp,b])
def check_value(bit):
    res = 0
    for i in range(len(data)):
        flag = True
        dd = data[i][0]
        for j in range(len_k):
            if bit[j] == '0' and dd[j] == '1':
                flag = False
                break
        if flag:
            
            res += data[i][1]
    return res
ans = check_value(bit_k)
tmp = []
for i in range(len_k):
    p = []
    if bit_k[i] == '1':
        p = tmp + ['0'] + ['1']*(len_k-1-i)
    else:
        tmp += bit_k[i]
        continue
    p = "".join(p)
    ans = max(ans, check_value(p))
    tmp += bit_k[i]
print(ans)

Solution (Python):
N,K = map(int,input().split())
K = "0"*(30-len(bin(K)[2:]))+bin(K)[2:]
A = [list(map(int,input().split())) for _ in range(N)]
B = [["0"*(30-len(bin(x[0])[2:]))+bin(x[0])[2:],x[1]] for x in A]
cmax = 0
cur = 0
while cur<30:
    if cur<29 and K[cur]=="1":
        cnt = 0
        x = K[:cur]+"0"
        for b in B:
            y,p = b[0],b[1]
            flag = 0
            for i in range(cur+1):
                if x[i]=="0" and y[i]=="1":
                    flag=1
                    break
            if flag==0:
                cnt += p
        cmax = max(cmax,cnt)
    elif cur==29 and K[cur]=="0":
        cnt = 0
        x = K[:]
        for b in B:
            y,p = b[0],b[1]
            flag = 0
            for i in range(cur+1):
                if x[i]=="0" and y[i]=="1":
                    flag=1
                    break
            if flag==0:
                cnt += p
        cmax = max(cmax,cnt)
    elif cur==29 and K[cur]=="1":
        cnt = 0
        x = K[:-1]
        for b in B:
            y,p = b[0],b[1]
            flag = 0
            for i in range(cur):
                if x[i]=="0" and y[i]=="1":
                    flag=1
                    break
            if flag==0:
                cnt += p
        cmax = max(cmax,cnt)
    cur += 1
print(cmax)

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


set_ = set([k])
for i in range(k.bit_length()):
    if (k >> i) & 1:
        mask1 = (1 << i) - 1
        mask2 = (1 << k.bit_length() + 1) - 1 - (1 << i)
        set_.add((k | mask1) & mask2)

ans = 0
for bit_state in set_:
    tmp_ans = 0
    for w, val in info:
        if bit_state | w == bit_state:
            tmp_ans += val
    ans = max(tmp_ans, ans)
print(ans)

Solution (Python):
N, K = map(int, input().split())
ABs = []
for i in range(N):
  A, B = map(int, input().split())
  ABs.append((A, B))
fs = [K]
for i in range(32):
  if K&(1<<i) != 0:
    f = (K^(1<<i))|((1<<i)-1)
    fs.append(f)
rs = []
for f in fs:
  r = 0
  for A, B in ABs:
    if f|A == f:
      r += B
  rs.append(r)
r = max(rs)
print(r)

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

for _ in range(N):
    a,b=map(int, input().split())
    cost.append(a)
    value.append(b)

ans.append(sum([value[j] for j in range(N) if (K|cost[j])==K]))

for i in range(30):
    tmp=0
    if ((K>>i)&1)==1:
        Kr=(K&~(1 << i))|((1 << i)-1)
        for j in range(N):
            if (Kr | cost[j])==Kr:
                tmp+=value[j]
        ans.append(tmp)

print(max(ans))

Solution (Python):
N,K=map(int,input().split())
AB=[]
for i in range(N):
    a,b=map(int,input().split())
    AB.append([a,b])
ans=sum([b for a,b in AB if K|a==K])

for i in range(int.bit_length(K)-1,0,-1):
    if not K &(1<<i):
        continue
    m=K & ~(1<<i)|(1<<i)-1
    s=sum([b for a,b in AB if m | a ==m])
    ans=max(s,ans)
print(ans)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N,K=MAP()
AB=[LIST() for i in range(N)]

ans=0
for i in range(N):
    if K|AB[i][0]==K:
        ans+=AB[i][1]

Kb=format(K, 'b')
for i, b in enumerate(Kb):
    if b=='1':
        
        Kb2=Kb[:i]+'0'+'1'*(len(Kb[i:])-1)
        k=int(Kb2, 2)
        sm=0
        for i in range(N):
            if k|AB[i][0]==k:
                sm+=AB[i][1]
        ans=max(ans, sm)
print(ans)

Solution (Python):
import sys
from functools import reduce


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

AB = []
for _ in range(N):
    AB.append([int(s) for s in input().split()])

ans = reduce(lambda v, ab: v + ab[1] if K | ab[0] == K else v, AB, 0)

for i in range(int.bit_length(K) - 1, 0, -1):
    if not K & (1 << i):
        continue
    km = K & ~(1 << i) | (1 << i) - 1
    anscand = reduce(lambda v, ab: v + ab[1] if km | ab[0] == km else v, AB, 0)
    ans = max(ans, anscand)
print(ans)

Solution (Python):
import sys


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

AB = []
for _ in range(N):
    AB.append([int(s) for s in input().split()])

ans = sum([b for a, b in AB if K | a == K])

for i in range(int.bit_length(K) - 1, 0, -1):
    if not K & (1 << i):
        continue
    km = K & ~(1 << i) | (1 << i) - 1
    anscand = sum([b for a, b in AB if km | a == km])
    ans = max(ans, anscand)
print(ans)

Solution (Python):
import sys


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

AB = []
for _ in range(N):
    AB.append([int(s) for s in input().split()])

ans = sum([b for a, b in AB if K | a == K])

for i in range(int.bit_length(K) - 1, 0, -1):
    if not K & (1 << i):
        continue
    km = K & ~(1 << i) | (1 << i) - 1
    anscand = sum([b for a, b in AB if km | a == km])
    ans = max(ans, anscand)
print(ans)

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

AB = []
for _ in range(N):
    AB.append([int(s) for s in input().split()])

ans = 0
kbin = bin(K)[2:]
for a, b in AB:
    if K | a == K:
        ans += b
for i in range(1, len(kbin)):
    if kbin[i - 1] == "0":
        continue
    kl = list(kbin)
    kl[i - 1] = "0"
    for j in range(i, len(kbin)):
        kl[j] = "1"
    km = int("".join(kl), 2)
    anscand = 0
    for a, b in AB:
        if km | a == km:
            anscand += b
    if ans < anscand:
        ans = anscand
print(ans)

Solution (Python):
N,K=map(int,input().split())
ad=dict()
al=ad.keys()
for i in range(N):
    a,b=map(int,input().split())
    if not a in ad:
        ad[a]=b
    else:
        ad[a]+=b

bk=bin(K)
lbk=len(bk)-2
k1=2**(lbk-1)-1
kl=[]
for i in range(lbk):
    ki=str(bk)[i+2]
    if ki=='1':
        kk=2**(lbk-1-int(i))
        kl.append((K-kk)|(kk-1))
kl.append(K)
kll=[0for i in range(len(kl))]
for i in range(len(kl)):

    for n in al:
        if n | kl[i]==kl[i]:
            kll[i]+=ad[n]
print(max(kll))

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

N,K = inpl()
L = K.bit_length()

koho = [K]
tmp = 0
for b in reversed(range(L)):
	if (K>>b) & 1:
		tmp += (1<<b)
		koho.append(tmp-1)

nums = [0]*len(koho)
for _ in range(N):
	A,B = inpl()
	for i,k in enumerate(koho):
		if k|A == k:
			nums[i] += B

print(max(nums))

Solution (Python):
n,k=map(int,input().split())
s=[tuple(map(int,input().split())) for _ in range(n)]
b=bin(k)[2:]
r=sum(b for a,b in s if k|a==k)
for i in range(len(b)-1):
    if b[i]=='0':
        continue
    l=int(b[:i]+'0'+'1'*(len(b)-i-1),2)
    r=max(r,sum(b for a,b in s if l|a==l))
print(r)

Solution (Python):
N, K = map(int,raw_input().split())
dict={K:0}
count = 0
k=bin(K)[2:]
a="111111111111111111111111111111" 
for i in k:
    if i == "1":
        dict[int(k[:count]+"0"+a[count+1:len(k)],2)] = 0
    count += 1
 
for i in range(0,N):
    a , b = map(int,raw_input().split())
    for j in dict:
        if j | a == j:
            dict[j] += b
        else:
            pass
        continue
M = 0
for i in dict:
    M = max(M,dict[i])
print M

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

l = []

kb = bin(k)
ll = [k]

for i in range(len(kb) - 2):
    if kb[i + 2] == '1':
        ll.append(int(kb[:i + 2] + '0' + '1' * (len(kb) - (i + 3)), 2))

for i in ll:
    ans = 0
    for j in range(n):
        if i == ab[j][0] | i:
            ans += ab[j][1]
        l.append(ans)

print(max(l))

Solution (Python):
def solve(K, ABs):
    if not ABs: return 0
    ansK = sum(b for a, b in ABs if (K | a) == K)
    pool = []
    for i in range(30, -1, -1):
        if (K & (1<<i)):
            pool.append(i)
    for p in pool:
        v = 1 << p
        KK = (K >> p) << p
        KKK = (K >> p)
        t = sum(b for a, b in ABs if (not(a & v) and ((a | KK) >> p) == KKK))
        if t > ansK:
            ansK = t
    return ansK
   

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

print(solve(K, ABs))

Solution (Python):
def solve(K, ABs):
    if not ABs: return 0
    ansK = sum(b for a, b in ABs if (K | a) == K)
    pool = []
    for i in range(30, -1, -1):
        if (K & (1<<i)):
            pool.append(i)
    for p in pool:
        v = 1 << p
        KK = (K >> p) << p
        KKK = (K >> p)
        t = sum(b for a, b in ABs if (not(a & v) and (a | KK) >> p == KKK))
        if t > ansK: ansK = t
    return ansK
   

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

print(solve(K, ABs))

Solution (Python):
n, k = [int(x) for x in input().strip().split()]
ls = []
for _ in range(n):
    ls.append(tuple(int(x) for x in input().strip().split()))

bk = bin(k)[2:]
cands = [k]
for i in range(len(bk)):
    if bk[i] == '1':
        cands.append(int(bk[:i] + '0' + '1'*(len(bk)-i-1), base=2))

m_ = len(cands)
max_ = [0] * m_

for a, b in ls:
    for i in range(m_):
        if a | cands[i] == cands[i]:
            max_[i] += b

print(max(max_))