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())
arr=[list(map(int,input().split())) for _ in range(n)]
ans1=0
ans2=0
pows=2**(k.bit_length()-1)
for a,b in arr:
  if a<=pows-1:
    ans1+=b
  if pows<=a<=k or a<=k-pows:
    ans2+=b
print(max(ans1,ans2))

Submission status: Wrong Answer

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

N,K = MI()

if K == 0:
    ans = 0
    for _ in range(N):
        a,b = MI()
        if a == 0:
            ans += b
    print(ans)
    exit()

k = K.bit_length()
AB = []

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

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

ANS = [0]*(k+1)  # A[i] = 上i桁の各桁がKの上i桁の各桁以下であり、i+1桁目が0である非負整数の価値の総和

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

print(max(ANS))

Submission status: Wrong Answer

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

N,K = MI()

if K == 0:
    ans = 0
    for _ in range(N):
        a,b = MI()
        if a == 0:
            ans += b
    print(ans)
    exit()

k = K.bit_length()
AB = []

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

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

ANS = [0]*(k+1)  # A[i] = 上i桁の各桁がKの上i桁の各桁以下であり、i+1桁目が0である非負整数の価値の総和

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

print(max(ANS)+x)

Submission status: Wrong Answer

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

N,K = MI()

if K == 0:
    ans = 0
    for _ in range(N):
        a,b = MI()
        if a == 0:
            ans += b
    print(ans)
    exit()

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 = [(K >> i) & 1 for i in range(k-1,-1,-1)]

ANS = [0]*(k+1)  # A[i] = 上i桁の各桁がKの上i桁の各桁以下であり、i+1桁目が0である非負整数の価値の総和

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

print(max(ANS))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
numk=[]
ans=0
nk=k
cntk=-1
for i in range(33):
    if nk==0 and cntk==-1:
        cntk=i
    numk.append(nk%2)
    nk//=2
num=[[] for _ in range(33)]
b=[]
for i in range(n):
    a,B=map(int,input().split())
    cnt=a
    b.append(B)
    for j in range(33):
        if cnt%2==1:
            num[j].append(i)
        cnt//=2
try1=[numk,[1]*(cntk-1)]
for i in range(33-len(try1[1])):
    try1[1].append(0)
if numk.count(1)>1:
    num10=[]
    cnt3=numk.count(1)
    cnt4=0
    for i in range(cntk-1):
        if numk[i]==1:
            cnt4+=1
        if cnt4<cnt3-1:
            num10.append(1)
        else:
            num10.append(0)
    num10.append(1)
    for i in range(33-len(num10)):
        num10.append(0)
    try1.append(num10)
for i in range(len(try1)):
    cnt10=0
    sumple=try1[i]
    yn=set()
    for j in range(len(sumple)):
        if sumple[j]==0:
            for k in range(len(num[j])):
                yn.add(num[j][k])
    for j in range(n):
        if j not in yn:
            cnt10+=b[j]
    ans=max(ans,cnt10)
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
numk=[]
ans=0
nk=k
cntk=-1
for i in range(33):
    if nk==0 and cntk==-1:
        cntk=i
    numk.append(nk%2)
    nk//=2
num=[[] for _ in range(33)]
b=[]
for i in range(n):
    a,B=map(int,input().split())
    cnt=a
    b.append(B)
    for j in range(33):
        if cnt%2==1:
            num[j].append(i)
        cnt//=2
try1=[numk,[1]*(cntk-1)]
for i in range(33-len(try1[1])):
    try1[1].append(0)
if numk.count(1)>1:
    num10=[]
    cnt3=numk.count(1)
    cnt4=0
    for i in range(cntk-1):
        if numk[i]==1:
            cnt4+=1
        if cnt4<cnt3-1:
            num10.append(1)
        else:
            num10.append(0)
    num10.append(1)
    for i in range(33-len(num10)):
        num10.append(0)
    try1.append(num10)
cnt9=sum(b)
for i in range(len(try1)):
    cnt10=0
    sumple=try1[i]
    yn=set()
    for j in range(len(sumple)):
        if sumple[j]==0:
            for k in range(len(num[j])):
                yn.add(num[j][k])
    for j in range(len(yn)):
        cnt10+=b[yn.pop()]
    ans=max(ans,cnt9-cnt10)
print(ans)

Submission status: Wrong Answer

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

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)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
numk=[]
ans=0
nk=k
for i in range(32):
    if nk==0:
        break
    numk.append(nk%2)
    nk//=2
num=[[] for _ in range(32)]
b=[]
cnt1=-1
for i in range(n):
    a,B=map(int,input().split())
    if a<=k:
        cnt=a
        cnt1+=1
        b.append(B)
        for j in range(32):
            if cnt==0:
                break
            if cnt%2==1:
                num[j].append(cnt1)
            cnt//=2
try1=[numk,[1]*(len(numk)-1)]
try1[1].append(0)
if numk.count(1)>2:
    num10=[]
    cnt3=numk.count(1)
    cnt4=0
    for i in range(len(numk)-1):
        if numk[i]==1:
            cnt4+=1
        if cnt4<cnt3-1:
            num10.append(1)
        else:
            num10.append(0)
    num10.append(1)
    try1.append(num10)
elif numk.count(1)==2:
    if numk[0]!=1:
        num10=[]
        cnt3=2
        cnt4=0
        for i in range(len(numk)-1):
            if numk[i]==1:
                cnt4+=1
            if cnt4<cnt3-1:
                num10.append(1)
            else:
                num10.append(0)
        num10.append(1)
        try1.append(num10)
cnt9=sum(b)
for i in range(len(try1)):
    cnt10=0
    sumple=try1[i]
    yn=set()
    for j in range(len(sumple)):
        if sumple[j]==0:
            for k in range(len(num[j])):
                yn.add(num[j][k])
    for j in range(len(yn)):
        cnt10+=b[yn.pop()]
    ans=max(ans,cnt9-cnt10)
print(ans)

Submission status: Wrong Answer

Solution code:
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(i, ans)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
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 N>>i & 1:
            K2=K-(1<<i)
            K2=K2 | ((1<<i)-1)
                    
            for k in range(N):#k番目の数を使うかどうか
                if K2 | A[k] == K2:
                    temp+=B[k]  
            ans=max(ans,temp)
           
    temp=0 
    for k in range(N):#k番目の数を使うかどうか
        if K | A[k] == K:
            temp+=B[k]
    ans=max(ans,temp)
    
    print(ans)
                    
                    
            
        
    
    

main()

Submission status: Wrong Answer

Solution code:
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
    import math
    M=len(bin(K))-2
    
    for i in range(M):
        temp=0
        if N>>i & 1:
            K2=K-(1<<i)
            K2=K2 | ((1<<i)-1)
                    
            for k in range(N):#k番目の数を使うかどうか
                if K2&A[k] == A[k]:
                    temp+=B[k]  
            ans=max(ans,temp)
           
    temp=0 
    for k in range(N):#k番目の数を使うかどうか
        if K&A[k] == A[k]:
            temp+=B[k]
    ans=max(ans,temp)
    
    print(ans)
                    
                    
            
        
    
    

main()

Submission status: Wrong Answer

Solution code:
print(0)

Submission status: Wrong Answer

Solution code:
N,K = list(map(int,input().split()))
AB = [list(map(int,input().split())) for i in range(N)]
bitK = bin(K)[2:]
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)

Submission status: Wrong Answer

Solution code:
N,K = list(map(int,input().split()))
AB = [list(map(int,input().split())) for i in range(N)]
bitK = bin(K)[2:]
ans = 0
for i in range(len(bitK)+1):
    score = 0
    if i==0:
        #print(bin(C-K))
        for j in range(N):
            if AB[j][0]|K == K:
                score+=AB[j][1]
    else:
        if bitK[i-1]=="1":
            check = (K >> (i-1))-1
            for j in range(N):
                if AB[j][0]>>(i-1)|check == check:
                    score+=AB[j][1]
    ans = max(score,ans)

print(ans)

Submission status: Wrong Answer

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

ans = 0
for i in range(len(bitK)+1):
    score = 0
    if i==0:
        #print(bin(C-K))
        for j in range(N):
            if AB[j][0]|K == K:
                score+=AB[j][1]
    else:
        bit = [int(bitK[j]) for j in range(i-1)] + [0] + [1 for j in range(len(bitK)-i)]
        L = 0
        for j in range(len(bit)):
            L*=2
            L += bit[j]
        #print(bin(L))
        for j in range(N):
            if AB[j][0]|L == L:
                score+=AB[j][1]
    ans = max(score,ans)

print(ans)

Submission status: Wrong Answer

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

C = 2**len(bitK)
ans = 0
for i in range(len(bitK)+1):
    score = 0
    if i==0:
        #print(bin(C-K))
        for j in range(N):
            if AB[j][0]&(C-K-1) == 0:
                score+=AB[j][1]
    else:
        bit = [int(bitK[j]) for j in range(i-1)] + [0] + [1 for j in range(len(bitK)-i)]
        L = 0
        for j in range(len(bit)):
            L*=2
            L += bit[j]
        #print(bin(L))
        for j in range(N):
            if AB[j][0]&(C-L-1) == 0:
                score+=AB[j][1]
    ans = max(score,ans)

print(ans)

Submission status: Wrong Answer

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

C = 2**len(bitK)
ans = 0
for i in range(len(bitK)+1):
    score = 0
    if i==0:
        #print(bin(C-K))
        for j in range(N):
            if AB[j][0]&(C-K-1) == 0:
                score+=AB[j][1]
    else:
        if bitK[i-1]=="1":
            bit = [int(bitK[j]) for j in range(i-1)] + [0] + [1 for j in range(len(bitK)-i)]
            L = 0
            for j in range(len(bit)):
                L*=2
                L += bit[j]
            #print(bin(L))
            for j in range(N):
                if AB[j][0]&(C-L-1) == 0:
                    score+=AB[j][1]
    ans = max(score,ans)

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
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)]
    msb = K.bit_length() - 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()

Submission status: Wrong Answer

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

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

log = len(bin(K))-2

def get_mask(K,b):
    j = 1
    res = 0

    for i in range(32):
        if i>=log:
            res+=j
        elif i==b:
            res += j
        elif i > b:
            if K & j == 0:
                res += j
        j *= 2
    return res


ans = 0
for i in range(log):
    mask = get_mask(K,i)
    #print(bin(mask))
    val = 0
    for a,b in A:
        if a & mask == 0:
            val += b
    ans = max(val,ans)

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def examD():
    N, K = LI()
    A = [0]*N; B = [0]*N
    for i in range(N):
        A[i],B[i] = LI()
    ans = 0; bi = 2
    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)
#        print(i,mask)
        now = 0
        for i in range(N):
            if A[i]&mask>0:
                continue
#            print(A[i],B[i])
            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
        #            print(A[i],B[i])
        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()

Submission status: Wrong Answer

Solution code:
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 = 0
        for j in range(i):
            if K&(1<<(bi-j))==0:
                mask += 2**(bi-j)
        mask += 2**(bi-i)
#        print(i,mask)
        now = 0
        for i in range(N):
            if A[i]&mask>0:
                continue
#            print(A[i],B[i])
            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()

Submission status: Wrong Answer

Solution code:
def examD():
    N, K = LI()
    A = [0]*N; B = [0]*N
    for i in range(N):
        A[i],B[i] = LI()
    ans = 0; bi = 3
    for i in range(bi+1):
        if K&(1<<(bi-i))==0:
            if i!=bi:
                continue
        mask = 0
        for j in range(i):
            if K&(1<<(bi-j))==0:
                mask += 2**(bi-j)
        mask += 2**(bi-i)
#        print(i,mask)
        now = 0
        for i in range(N):
            if A[i]&mask>0:
                continue
#            print(A[i],B[i])
            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()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
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, -1, -1):
        mask = K
        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()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
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, -1, -1):
        mask = K
        if mask & 1 << i:
            mask -= 1 << i
        for j in range(i):
            mask |= 1 << j
        cand = 0
        for a, b in AB:
            if (a | mask) == mask:
                cand += b
        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()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
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 range(len(l)):
        li = l[i]
        p |= (1<<li)-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


#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
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 range(len(l)):
        li = l[i]
        if i == 0:
            np = (1<<li)-1
            res = 0
            for a,b in v:
                if a&np == a:
                    res += b
            if ans < res:
                ans = res
        p |= 1<<li
        res = 0
        for a,b in v:
            if a&p == a:
                res += b
        if ans < res:
            ans = res
        if i < len(l)-1:
            nli = l[i+1]
            np = p|((1<<nli)-1)
            res = 0
            for a,b in v:
                if a&np == a:
                    res += b
            if ans < res:
                ans = res
    print(ans)
    return


#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
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 range(len(l)):
        li = l[i]
        p |= 1<<li
        res = 0
        for a,b in v:
            if a&p == a:
                res += b
        if ans < res:
            ans = res
        if i < len(l)-1:
            nli = l[i+1]
            np = p|((1<<nli)-1)
            res = 0
            for a,b in v:
                if a&np == a:
                    res += b
            if ans < res:
                ans = res
    print(ans)
    return


#Solve
if __name__ == "__main__":
    solve()