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



Sample input:
3 5
3 3
4 4
2 5


Sample output:
8

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(key=lambda x: x[1], reverse=True)
ans = 0
x = 0
for a, b in AB:
    if x | a <= K:
        x = x | a
        ans += b
    
print(ans)

Submission status: Wrong Answer

Solution code:
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=[]
    m=(1<<ek)-1
    ms=m>>1
    for i in range(ek):
        m0=((m>>i)|k)&(m-(1<<(ek-i-1)))
        cand.append(sum([e[1] for e in ab if e[0]|m0==m0]))
    cand.append(sum([e[1] for e in ab if e[0]|k==k]))
    print(max(cand))

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
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:
            #print("tmp:{} bit{}".format(tmp, bit))
            res += data[i][1]
    return res
ans = 0
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)

Submission status: Wrong Answer

Solution code:
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:
            #print("tmp:{} bit{}".format(tmp, bit))
            res += data[i][1]
    return res
ans = 0
tmp = []
for i in range(len_k):
    p = []
    if bit_k[i] == '1':
        p = tmp + ['0'] + ['1']*(len_k-1-i)
    else:
        p = bit_k
    p = "".join(p)
    ans = max(ans, check_value(p))
    tmp += bit_k[i]
print(ans)

Submission status: Wrong Answer

Solution code:
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:
            #print("tmp:{} bit{}".format(tmp, bit))
            res += data[i][1]
    return res
ans = 0
tmp = []
for i in range(len_k):
    p = list(copy.deepcopy(bit_k))
    if p[i] == '1':
        p = tmp + ['0'] + ['1']*(len_k-1-i)
        p = "".join(p)
    else:
        p = "".join(p)
    ans = max(ans, check_value(p))
    tmp += bit_k[i]
print(ans)

Submission status: Wrong Answer

Solution code:
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:
            #print("tmp:{} bit{}".format(tmp, bit))
            res += data[i][1]
    return res
ans = 0
tmp = []
for i in range(len_k):
    p = list(copy.deepcopy(bit_k))
    if p[i] == '1':
        p = tmp + ['0'] + ['1']*(len_k-1-i)
        p = "".join(p)
    else:
        p = "".join(p)
    ans = max(ans, check_value(p))
    tmp += p[i]
print(ans)

Submission status: Wrong Answer

Solution code:
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):
            #print("{} {}".format(bit, data[i]))
            if bit[j] == '0' and dd[j] == '1':
                flag = False
                break
        if flag:
            #print("tmp:{} bit{}".format(tmp, bit))
            res += data[i][1]
    return res
ans = 0
for i in range(len_k):
    p = list(copy.deepcopy(bit_k))
    if p[i] == '1':
        p = p[:i] + ['0'] + ['1']*(len_k-1-i)
        p = "".join(p)
    else:
        p = "".join(p)
    ans = max(ans, check_value(p))
print(ans)

Submission status: Wrong Answer

Solution code:
import copy
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):
            #print("{} {}".format(bit, data[i]))
            if bit[j] == '0' and dd[j] == '1':
                flag = False
                break
        if flag:
            #print("tmp:{} bit{}".format(tmp, bit))
            res += data[i][1]
    return res
ans = 0
for i in range(len_k):
    p = list(copy.deepcopy(bit_k))
    if p[i] == '1':
        p = p[:i] + ['0'] + ['1']*(len_k-1-i)
        p = "".join(p)
    else:
        p = "".join(p)
    ans = max(ans, check_value(p))
print(ans)

Submission status: Wrong Answer

Solution code:
import copy
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:
        data.append([a,b])
def check_value(bit):
    res = 0
    for i in range(len(data)):
        tmp = format(data[i][0], 'b')
        tmp = tmp.zfill(len_k)
        flag = True
        for j in range(len_k):
            if bit[j] == '0' and tmp[j] == '1':
                flag = False
                break
        if flag:
            #print("tmp:{} bit{}".format(tmp, bit))
            res += data[i][1]
    return res
ans = 0
for i in range(len_k):
    p = list(copy.deepcopy(bit_k))
    if p[i] == '1':
        p = p[:i] + ['0'] + ['1']*(len_k-1-i)
        p = "".join(p)
    else:
        p = "".join(p)
    ans = max(ans, check_value(p))
print(ans)

Submission status: Wrong Answer

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

AB_=[]
for i in AB:
    if i==0:
        continue
    k=bin(i[0])[2:].zfill(30)
    AB_.append([k,i[1]])
AB=AB_
l=len(AB)
 
k=bin(K)[2:].zfill(30)
ans=0
for i in range(30):
    if k[i]=="1":
        t=k[:i]+"0"
        sum=0
        for j in range(l):
            if int(t)|int(AB[j][0][:i+1])<=int(t):
                sum+=AB[j][1]
        ans=max(ans,sum)
sum=0
t=k
for j in range(l):
    if int(t)|int(AB[j][0])<=int(t):
        sum+=AB[j][1]
ans=max(ans,sum)
print(ans)

Submission status: Wrong Answer

Solution code:
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()
print(bin(K))

koho = [K]
tmp = 0
for b in reversed(range(L)):
	if (K>>b) & 1:
		print(b)
		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))

Submission status: Wrong Answer

Solution code:
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
    p=int(b[:i]+'0'*(len(b)-i),2)
    q=int('1'*(len(b)-i-1),2)
    r=max(r,sum(b for a,b in s if a<=q or p<=a<=p+q))
print(r)

Submission status: Wrong Answer

Solution code:
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[0]=='0':
        continue
    p=int(b[:i]+'0'*(len(b)-i),2)
    q=int('1'*(len(b)-i-1),2)
    r=max(r,sum(b for a,b in s if a<=q or p<=a<=p+q))
print(r)

Submission status: Wrong Answer

Solution code:
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)])] = 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

Submission status: Wrong Answer

Solution code:
import itertools
n,k = map(int,input().split())
arr = [list(map(int,input().split())) for i in range(n)]
nums = []

dic = {}
for i in arr:
    dic[i[0]] = i[1]
ans = 0
tmp = 0
for i in arr:
    nums.append(i[0])
for i in range(n):
    for c in itertools.permutations(nums,i):
        if sum(c) <= k:
            for j in range(len(c)):
                tmp += dic[c[j]]
            if tmp > ans:
                ans = tmp
            tmp = 0
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=list(map(int,input().split(' ')))

a=[0 for i in range(n)]
b=[0 for i in range(n)]
m=0
for i in range(n):
    a[i],b[i]=list(map(int,input().split(' ')))
    j=0
    while j<len(a)-1:
       if a[i]+a[j]<=k and m<b[i]+b[j] :
           m=b[i]+b[j]
       j+=1
print(m)

Submission status: Wrong Answer

Solution code:
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
        t = sum(b for a, b in ABs if (not(a & v) and a <= KK))
        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))

Submission status: Wrong Answer

Solution code:
n,k=list(map(int,input().split(' ')))

a=[0 for i in range(n)]
b=[0 for i in range(n)]
m=0
for i in range(n):
    a[i],b[i]=list(map(int,input().split(' ')))

i=0
j=0
while i <len(a):
    j=i+1
    while j<len(a):
        if a[i]+a[j]<=k and m<b[i]+b[j] :
            m=b[i]+b[j]
        j+=1
    i+=1
print(m)

Submission status: Wrong Answer

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

rows=[input().split() for _ in range(N)]

data={int(row[0]):int(row[1]) for row in rows}

res=0
for d in range(K):
    tmp_res=0
    for key in data.keys():
        if(key|d==d):
            tmp_res+=data[key]
    #print(d,tmp_res)
    if(tmp_res>res):
        res=tmp_res
print(res)

Submission status: Wrong Answer

Solution code:
import sys
N, K = map(int, input().split())
sum = 0
for n in range(N):
    a, b = map(int, input().split())
    if (a <= K) and (K == K | a):
        sum += b

print(sum)

Submission status: Wrong Answer

Solution code:
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)
        else:
            if pool:
                break
    for p in pool:
        v = 1 << p
        t = sum(b for a, b in ABs if not(a & v))
        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))

Submission status: Wrong Answer

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

dp=[[0 for i in range(k+1)] for j in range(n+1)]
w=[]
v=[]
for i in range(n):
    ww,vv = map(int,input().split())
    w.append(ww); v.append(vv)

for i in range(1,n+1):
    for j in range(0,k+1):
        dp[i][j] = dp[i-1][j]
        if j - w[i-1]>=0:
            dp[i][j] = max(dp[i][j], dp[i-1][j-w[i-1]] + v[i-1])

ans = max(dp[n])
print(ans)

Submission status: Wrong Answer

Solution code:
def solve(K, ABs):
    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)
        else:
            if pool:
                break
    for p in pool:
        v = 1 << p
        t = sum(b for a, b in ABs if not(a & v))
        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))

Submission status: Wrong Answer

Solution code:
def solve(K, ABs):
    ansK = sum(b for a, b in ABs if (K | b) == K)
    pool = []
    for i in range(30, 0, -1):
        if (K & (1<<i)):
            pool.append(i)
        else:
            if pool:
                break
    for p in pool:
        v = 1 << p
        t = sum(b for a, b in ABs if not(a & v))
        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))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from copy import deepcopy

N,K=map(int,input().split())
AB=[0]*N
dic=defaultdict(int)
for i in range(N):
    a,b=map(int,input().split())
    if a in dic.keys():
        AB[dic[a]]=[a,AB[dic[a]][1]+b]
    else:
        dic[a]=i
        AB[i]=[a,b]
AB_=[]
for i in AB:
    if i==0:
        continue
    k=bin(i[0])[2:].zfill(30)
    AB_.append([k,i[1]])
AB=AB_
l=len(AB)

k=bin(K)[2:].zfill(30)
ans=0
for i in range(30):
    if k[i]=="1":
        t=k[:i]+"0"
        sum=0
        for j in range(l):
            if int(t)|int(AB[j][0][:i+1])<=int(t):
                sum+=AB[j][1]
        ans=max(ans,sum)
sum=0
t=k
for j in range(l):
    if int(t)|int(AB[j][0])<=int(t):
        sum+=AB[j][1]
ans=max(ans,sum)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)  # remove i-th bit
        x = x | ((1 << i) - 1)  # add 1 to j-th bit (j<i)
        k_subset.append(x)

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

print(ans)

Submission status: Accepted

Solution code:
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)
# print(k_bin)
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
        # print(i, bin(x), cand)
        ans = max(ans, cand)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
#print(Kbit)

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]
#print(answer)

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]
    #print(K2bit,K2)
      
    neq_ans=0
    for i in range(N):
      if K2|alist[i]==K2:
        neq_ans+=blist[i]
    #print(neq_ans)
    answer=max(answer,neq_ans)
    
print(answer)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math, cmath
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import _heapify_max, _heappop_max, _siftdown_max
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    Num = Union[int, float]
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    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 _heappush_max(h, item): h.append(item); _siftdown_max(h, 0, len(h)-1)


    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)
        # print(f'pattern_int: {pattern_int} pattern: {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)
    # debug(b)
    # debug(flag)

    for i in flag:
        pattern = b[:]
        # 下から i 桁目を 1 -> 0 へ変更した場合、それより小さい桁は任意 (1 をとれる)
        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()

Submission status: Accepted

Solution code:
# integrotS
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)

Submission status: Accepted

Solution code:
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:
            #print("tmp:{} bit{}".format(tmp, bit))
            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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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':
        # あるビットが1だったら、そこは0にしてそこから先を全部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)