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: Accepted

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

judgeNum = pow(2,30)-1

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

print(res)

Submission status: Accepted

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

Submission status: Accepted

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


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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

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

# bitwise-orがK以下になるには
# ある桁kが存在し，K & (1 << k) == 1 and n & (1 << k) == 0 かつ上位kビットのみでK以下

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

    if maskN % 2 == 1:
        return False

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

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

print(ans)

Submission status: Accepted

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


def main():
    n, k = map(int, input().split())
    ab = [tuple(map(int, input().split())) for _ in range(n)]
    ans = 0
    # とりあえずansの候補
    for a, b in ab:
        if k&a == a:
            ans += b
    
    i = 1
    while i<=k:
        # 下のbitから全部1に変えていく
        if k&i:
            k ^= i
            tmp = 0
            for a, b in ab:
                if k&a == a:
                    tmp += b
            if ans < tmp:
                ans = tmp
        k ^= i
        i *= 2
    
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

def solve(num):
    res = 0
    for i in range(n):
        if (info[i][0] | num) == num:
            res += info[i][1]
    return res


k = bin(k)[2::]
ans = 0
num = int(k,2)
ans = solve(num)

for i in range(len(k)):
    if k[i] == "1":
        num = int(k[0:i]+"0"+(len(k)-i-1)*"1", 2)
        ans = max(ans, solve(num))
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
int_list = []
for _ in range(N):
    A, B = map(int, input().split())
    int_list.append([A, B])

K_bin = bin(K)[2:]
max_len = len(K_bin)
for i in range(N):
    int_list[i] = (bin(int_list[i][0])[2:].zfill(max_len), int_list[i][1])

or_list = [K_bin]
for i in range(max_len):
    if K_bin[i] == '1':
        or_list.append(K_bin[:i] + '0' + '1' * (max_len - i - 1))

ans = 0
for k in or_list:
    ans_k = 0
    for A, B in int_list:
        if len(A) > max_len:
            continue
        ok = 1
        for j, a in enumerate(A):
            if a == '1' and k[j] == '0':
                ok = 0
                break
        if ok:
            ans_k += B
    ans = max(ans, ans_k)

print(ans)

Submission status: Accepted

Solution code:

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

AB.sort(key = lambda x:x[0])
import math 

K2 = bin(K)
K2 = K2[2:]

L = len(K2)

ans = 0
zeroidx = [L-i-1 for i in range(len(K2)) if K2[i] == '0']

for a,b in AB:
    if a > K: break
    for z in zeroidx:
        if (a>>z)%2 == 1:
            break
    else:
        ans += b
    
MAX = ans
    


for i in range(len(K2)):
    if K2[i] == '0':continue
    
    Knew2 = K2[:i] +'0' +  ''.join(map(str,['1']*(len(K2)-1-i)))
    Knew = int(Knew2,2)
    zeroidx = [L-i-1 for i in range(len(K2)) if Knew2[i] == '0']
    ans = 0
    for a,b in AB:
        if a > Knew: break
        for z in zeroidx:
            if (a>>z)%2 == 1:
                break
        else:
            ans += b
        
    MAX = max(MAX,ans)
    
print(MAX)

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
l = [tuple(map(int, input().split())) for _ in range(n)]
k_ = k.bit_length()
ans = sum(b for a,b in l if k|a == k)
for i in range(k_):
  if k&2**i == 0:
    continue
  nk = ((k>>i)<<i) - 1
  ac = 0
  for a,b in l:
    if nk|a == nk:
      ac += b
  if ac > ans:
    ans = ac
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
def calc(k):
    ret=0
    for a,b in AB:
        if a|k==k:
            ret+=b
    return ret

n,k=map(int,input().split())
AB=[tuple(map(int,input().split())) for _ in range(n)]
ans=calc(k)
b=k.bit_length()
for d in range(1,b):
    tmp=k>>d
    if tmp%2==0:
        continue
    tmp<<=d
    tmp-=1
    ans=max(ans,calc(tmp))
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=[]
B=[]
for i in range(N):
	a,b=map(int,input().split())
	A+=a,
	B+=b,
z=0
for i in range(31):
	if K>>i&1 or i==30:
		S=(K>>i<<i)-1if i<30else K
		x=0
		for j in range(N):
			if (S|A[j])==S:
				x+=B[j]
		z=max(z,x)
print(z)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

N,K = map(int,input().split())
A,B = np.array([input().split() for _ in range(N)], dtype=np.int64).T

ks = [K]
x = K
while x:
    ks.append(x-1)
    x -= x&(-x)

answer = 0
for k in ks:
    select = (A & k == A)
    answer = max(answer, B[select].sum())

print(answer)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
*AB, = [list(map(int,input().split())) for _ in [0]*N]
bK = bin(K)[2:]
l = len(bK)
def f(x): return sum(b for a,b in AB if a | x == x )

x = ""
ans = f(K)
for k in bK:
    if k=="1":
        n = int((x + "0" + "1"*l)[:l],2)
        ans = max(ans,f(n))
        x+="1"
    else:
        x += "0"

print(ans)

Submission status: Accepted

Solution code:
# XORだと思っていた ORだった
n, k = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n)]

ans = 0
for a, b in ab:
    if a | k == k:
        ans += b
for i in range(30):
    if k & 1<<i != 1<<i:
        continue
    #print(~(1<<(i+1) - 1))
    l = k^(1<<i) | (1<<i) - 1
    #print(bin(l))
    s = 0
    for a, b in ab:
        if a | l == l:
            s += b
    ans = max(ans, s)
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=[0 for i in range(N)]
B=[0 for i in range(N)]
for i in range(N):
    A[i],B[i]=map(int,input().split())
S=bin(K)
X=[K]
M=len(S)-2
for k in range(1,M+1):
    if S[-k]=="0":continue
    tmp=S[:-k]+"0"+"1"*(k-1)
    X.append(int(tmp,2))
ans=0
for n in X:
    tmp=0
    for i in range(N):
        if A[i]&n==A[i]:
            tmp+=B[i]
    ans=max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
def issubset(x,y):
    #a<<bならtrue
    if len(x)>len(y):
        return False
    for i in range(1,len(x)+1):
        if (x[-i],y[-i])==("1","0"):
            return False
    return True
N,K=map(int,input().split())
A=[0 for i in range(N)]
B=[0 for i in range(N)]
for i in range(N):
    A[i],B[i]=map(int,input().split())
    A[i]=bin(A[i])[2:]
Ks=bin(K)[2:]
Kl=[Ks]
for i,c in enumerate(Ks):
    if c=="1":
        Kl.append(Ks[:i]+"0"+"1"*(len(Ks)-i-1))
ans=0
for k in Kl:
    tmp=0
    for i in range(N):
        if issubset(A[i],k):
            tmp+=B[i]
    ans=max(tmp,ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
N, K = map(int, input().split())
candi = []
p = 0
for i in range(30, -1, -1):
    if 2**i & K == 0:
        p += 2**i
        continue
    else:
        candi.append(p + 2**i)
candi.append(p)
AB = [tuple(map(int, input().split())) for _ in range(N)]
ans = 0

for c in candi:
    cans = 0
    for a, b in AB:
        if a & c:
            continue
        cans += b
    ans = max(ans, cans)
print(ans)

Submission status: Accepted

Solution code:
N,K = [ int(it) for it in input().split() ]
li = [ [ int(it) for it in input().split() ] for i in range(N) ]

kbit = []
k = K
for i in range(100000000):
  if (k == 0):
    break
  kbit.append( k%2 )
  k//=2
keta = len(kbit)

def chk(c):
  #print (c)
  s = 0
  for k,v in li:
    if ( (c^k)|c == c ):
      #print ( k,v,"ok" )
      s += v
  return s

ma = 0

if (K<100):
  for i in range(K+1):
  	ma = max(ma, chk(i))
else:
  ma = max(ma, chk( 0 ))
  ma = max(ma, chk( 1 ))
  ma = max(ma, chk( 2 ))
  ma = max(ma, chk( 3 ))
  ma = max(ma, chk( 4 ))
  ma = max(ma, chk( (1<<(keta-1))-1) )
  ma = max(ma, chk ( K ) )

  for i in range(keta):
    if ( kbit[keta-1-i] == 0 ):
      continue
    else:
      bit = [0]*(keta)
      for j in range(keta):
        if (i<j):
          bit[keta-1-j]=1
        elif (j<i):
          bit[keta-1-j]=kbit[keta-1-j]
        else:
          bit[keta-1-j]=0

      v = 0
      for j in range(keta):
        if (bit[j]==1):
          v += 2**(j)
      #print ( v , bit )
      ma = max(ma, chk ( v ) )
print ( ma )

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
goods=[tuple(map(int,input().split())) for i in range(N)]
ALL=0
from collections import defaultdict
data=defaultdict(int)
B=0
KS=bin(K)[2:]
for a,b in goods:
    astr=bin(a)[2:]
    if len(astr)>len(KS):
        continue
    else:
        B+=b
        for i in range(-1*len(astr),0):
            if astr[i]==KS[i]=="1":
                data[i]+=b
            elif astr[i]=="1" and KS[i]=="0":
                data[i]+=b
                break
ans=0
for i in range(-1*len(KS),0):
    if KS[i]=="1":
        ans=max(B-data[i],ans)
    else:
        B-=data[i]
ans=max(B,ans)
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
c = []
for i in range(n):#h:高さ
    c.append([int(m) for m in input().split()])

x = 0
candi = [k]
for i in range(31, -1, -1):
    if k & (x + 2 ** i) == x + 2 ** i:
        candi.append(x + 2 ** i - 1)
        x += 2 ** i

ans = 0
tmpans = 0
for can in candi:
    for i in range(n):
        if can & c[i][0] == c[i][0]:
            tmpans += c[i][1]
    ans = max(ans, tmpans)
    tmpans = 0
print(ans)

Submission status: Accepted

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

ans = 0
for i, b in enumerate(bin(K+1)[2:][::-1]):
    if b == '0': continue
    v = 0
    C = (K+1) & ~((1<<i)-1)
    mask = ~(C-1)
    for A, B in ABs:
        if A < C and A & mask == 0:
            v += B
    ans = max(ans, v)

print(ans)

Submission status: Accepted

Solution code:
inpl = lambda: list(map(int,input().split()))
N, K = inpl()
A = []
B = []
for _ in range(N):
    a, b = inpl()
    A.append(a)
    B.append(b)

L = K + 1
ans = 0
for i in range(31):
    L_shift = L >> i
    if L_shift & 1 == 0:
        continue
    else:
        L_shift ^= 1
    value = 0
    for j in range(N):
        a_shift = A[j] >> i
        if (a_shift | L_shift) == L_shift:
            value += B[j]
    ans = max(ans,value)

print(ans)

Submission status: Accepted

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]

n, k = map(int, input().split())
d = 31
z = [list(map(int, input().split())) for _ in range(n)]
used = [True for _ in range(n)]
dp = [[0 for _ in range(2)] for _ in range(d)]
dp[d-1][1] = sum([x[1] for x in z])
for i in range(d-2, -1, -1):
	if (k>>i) % 2 == 1:
		dp[i][1] = dp[i+1][1]
		tmp = 0
		for j in range(n):
			if used[j] == True and (z[j][0]>>i) % 2 == 0:
				tmp += z[j][1]
		if tmp == dp[i+1][1]:
			dp[i][1] = 0
			used = [False] * n
		dp[i][0] = max(tmp, dp[i+1][0])
	else:
		dp[i][1] = dp[i+1][1]
		for j in range(n):
			if used[j] == True and (z[j][0]>>i) % 2 == 1:
				used[j] = False
				dp[i][1] -= z[j][1]
		dp[i][0] = dp[i+1][0]
print(max(dp[0]))

Submission status: Accepted

Solution code:
# prd_xxx様のコードを参考: https://atcoder.jp/contests/tenka1-2017/submissions/1640474
N, K = map(int, input().split())
Items = [list(map(int, input().split())) for i in range(N)]


bs = bin(K)[2:].zfill(31)
masks = [bs]
for k in range(31):
    # Kのk-bit目が1ならば、k-bit目を0にして、そこより下を全て1にできる
    if bs[k] == '1':
        mask = bs[:k] + '0' + '1' * (30 - k)
        masks.append(mask)


ans = 0
for mask in masks:
    mask = int(mask, base=2)
    tmp = 0
    for a, b in Items:
        # orしても変わらない → aはmaskの部分集合
        if mask | a == mask:
            tmp += b
    ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,k = li()

ab = []
for _ in range(n):
    a,b = li()
    if a <= k:
        ab.append((a,b))

binn = len(bin(k))-2
bink = bin(k)[2:]

# binの候補を挙げる
cands = [bink]
for i, s in enumerate(list(bink)):
    if int(s):
        cands.append(bink[:i] + "0" + "1"*(binn-i-1))
        
ans = 0
for cand in cands:
    tmp = 0    
    cand = int("0b"+cand, 0)
    
    for a, b in ab:

        if cand | a <= cand:
            tmp += b
                
    ans = max(ans, tmp)
    
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,k = li()

# aをbin文字列で、bを数値で管理する
alis = []
blis = []
for _ in range(n):
    a,b = li()
    if a <= k:
        alis.append(a)
        blis.append(b)

binn = len(bin(k))-2
bink = bin(k)[2:]
binas = [bin(ai)[2:].zfill(binn) for ai in alis]


# binの候補を挙げる
cands = [bink]
for i, s in enumerate(list(bink)):
    if int(s):
        cands.append(bink[:i] + "0" + "1"*(binn-i-1))
        
ans = 0
for cand in cands:
    tmp = 0    
    cand = int("0b"+cand, 0)
    
    for a, b in zip(alis, blis):

        if cand | a <= cand:
            tmp += b
                
    ans = max(ans, tmp)
    
print(ans)

Submission status: Accepted

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

ab = [[int(i) for i in input().split()] for _ in range(n)]

if k <= 1:
    ans = 0
    for a, b in ab:
        if a <= k:
            ans += b
    print(ans)
    exit()

d = 2
for i in range(31):
    if k < d:
        d //= 2
        break
    d *= 2

ans = 0
for a, b in ab:
    if a | k <= k:
        ans += b

while d > 0:
    temp_k = (k - d) | (d - 1)
    temp_ans = 0
    for a, b in ab:
        if a | temp_k <= temp_k:
            temp_ans += b
    ans = max(ans, temp_ans)
    #print(d, temp_k, temp_ans)
    d //= 2

print(ans)

Submission status: Accepted

Solution code:

import sys
from collections import deque
import copy
import heapq
import math

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, K] = [long(input_raw[0]), long(input_raw[1])]
    A_list = []
    B_list = []
    for i in range(N):
        input_raw = read_func().strip().split()
        [A, B] = [long(input_raw[0]), long(input_raw[1])]
        A_list.append(A)
        B_list.append(B)

    if K == 0:
        value = 0
        for i in range(N):
            if A_list[i] == 0:
                value += B_list[i]
        print value
        exit()
    max_value = 0
    for r in range(int(math.log(K, 2))+1 + 1):
        if ((K>>r) & 0x01) == 1 or r > int(math.log(K, 2)):
            if r <= int(math.log(K, 2)):
                Kr = ((K & ~(0x01<<r)) | ((0x01<<r) - 1))
            else:
                Kr = K
            value = 0
            for i in range(N):

                if (A_list[i] | Kr) == Kr:
                    value += B_list[i]
            max_value = max(max_value, value)

    print max_value



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

if __name__ == '__main__':
    N, K = list(map(int, input().split()))
    integer_value = []
    for i in range(N):
        integer, value = list(map(int, input().split()))
        integer_value.append((integer, value))
    if K == 0:
        r = 0
    else:
        r = int(math.log(K, 2))
    max_value = 0
    for i in range(r + 1):
        # print((K >> i) & 0b1)
        if not ((K >> i) & 0b1):
            continue

        tmp_sum = 0

        mask = 1
        for j in range(i):
            mask = (mask << 1) + 1
        Ki = (K | mask) - 2 ** i

        for tmp_int, tmp_val in integer_value:
            if Ki | tmp_int == Ki:
                tmp_sum += tmp_val

        # print(str(tmp_sum) + " " + str(i))
        if max_value < tmp_sum:
            max_value = tmp_sum

    # K の場合
    K_val = 0
    for tmp_int, tmp_val in integer_value:
        if K | tmp_int == K:
            K_val += tmp_val
    # print("max_val" + str(max_value))
    # print("K_val" + str(K_val))
    if K_val < max_value:
        print(max_value)
    else:
        print(K_val)

Submission status: Accepted

Solution code:
#get targets
def get (K):
	ret = [K]
	for r in range(31):
		if ((K >> r) & 1) == 1 :
			tmp = K
			tmp &= (~(1 << r))
			tmp |= (1 << r) - 1
			ret.append(tmp);
	return ret

#input
N, K = map(int, input().split())
items = []
for steps in range(N):
	A, B = map(int, input().split())
	items.append([A, B])
#process
targets = get(K)
answer = 0
for target in targets:
	cur = 0
	for a, b in items:
		if(target | a == target):
			cur += b;
	answer = max(answer, cur)

print(answer)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def pf(s):
    print(s, flush=True)

def main():
    n,k = LI()
    t = [LI() for _ in range(n)]

    d = {}
    d[k] = 0
    j = 0
    for i in range(30,-1,-1):
        ii = 2**i
        if k & ii > 0:
            d[j+ii-1] = 0
            j += ii
    js = d.keys()
    for a,b in t:
        for j in js:
            if j & a ^ a == 0:
                d[j] += b
    return max(d.values())




print(main())

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A, B, a = [0] * N, [0] * N, [''] * N
for i in range(N):
    A[i], B[i] = map(int, input().split())
    a[i] = str(bin(A[i])[2:]).rjust(30, '0')
k = str(bin(K)[2:]).rjust(30, '0')

ans = 0

s = k.index('1') if '1' in k else 30
for r in range(s, 30 + 1):
    tmp = 0
    for i in range(N):
        if r < 30 and k[r] == '0':
            continue
        affordable = True
        for j in range(r):
            if k[j] == '0' and a[i][j] == '1':
                affordable = False
        if r < 30 and a[i][r] == '1':
            affordable = False
        if affordable:
            tmp += B[i]
    ans = max(ans, tmp)

print(ans)

Submission status: Accepted

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

def it():
  i = 1
  while i <= K:
    if K & i:
      j = (K^i)|(i-1)
      yield sum(b for a,b in items if a&~j==0)
    i <<= 1
  yield sum(b for a,b in items if a&~K==0)

print(max(it()))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# 動画解説を見る
#
# 110101以下の数は、以下のいずれかである
#
# 110101
# 110100 (1を一つ選んで0にする、それ以下の桁はなんでもよいので?とする)
# 1100??
# 10????
# 0?????
#
# 上の各パターンについて条件を満たすものをそれぞれ探し、maxをとる
# 各パターンでは、0になるべき桁が必ず0になるようにする
#
# 実装上は、?をすべて1で置換。orをとった結果、0の箇所に1が来ないようにする
#
# 110101
# 110011
# 101111
# 011111



import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import re
import string

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

ret = 0

# orをとって 110101 以下になるもののみretに足す
for n in range(N):
    if K | A[n] == K:
        ret += B[n]

# Kの下位ビットから順に見ていき、もし1があれば、その桁を0にして、その桁より下位をすべて1にする
for i in range(31):
    # n番目の桁が0なら、1にする
    if (K >> i) & 1 == 0:
        K |= (1 << i)
    else:
        # n番目の桁が1なら、0にする
        K ^= (1 << i)

        local_ret = 0
        for n in range(N):
            if K | A[n] == K:
                local_ret += B[n]
        ret = max(ret, local_ret)

        # また1に戻す
        K |= (1 << i)


print(ret)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = [tuple(int(x) for x in input().split()) for _ in range(N)]
A = [(a, b) for a, b in A if a <= K]
L = K.bit_length()
ans = sum(b for a, b in A if (a | K) <= K)
for i in reversed(range(L)):
    bit = (1 << i) & K
    if bit != 1:
        cand = 0
        bor = 0
        tmp_K = K & ~(1 << i) | ((1 << i) - 1)
        ans = max(ans, sum(b for a, b in A if (a | tmp_K) <= K))
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# 110101以下の数は、以下のいずれかである
#
# 110101
# 110100 (1を一つ選んで0にする、それ以下の桁はなんでもよいので?とする)
# 1100?? 
# 10????
# 0?????
#
# 上の各パターンについて条件を満たすものをそれぞれ探し、maxをとる
# 各パターンでは、0になるべき桁が必ず0になるようにする
#
# 実装上は、?をすべて1で置換。orをとっても以下の数値を超えないようにする
#
# 110101
# 110011
# 101111
# 011111
#


import array
from bisect import *
from collections import *
import fractions
import heapq 
from itertools import *
import math
import re
import string

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

ret = 0

# orをとって 110101 以下になるもののみretに足す
for n in range(N):
    if K | A[n] == K:
        ret += B[n]

# Kの下位ビットから順に見ていき、もし1があれば、その桁を0にして、その桁より下位をすべて1にする
for n in range(31):
    # n番目の桁が0なら、1にする
    if (K >> n) & 1 == 0:
        K |= (1 << n)
    else:
        # n番目の桁が1なら、0にする
        K ^= (1 << n)

        local_ret = 0
        for m in range(N):
            if K | A[m] == K:
                local_ret += B[m]
        ret = max(ret, local_ret)

        # また1に戻す
        K |= (1 << n)


print(ret)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def inpl(): 
    return tuple(map(int, input().split()))

N, K = inpl()
numbers = []

for _ in range(N):
    A, B = inpl()
    numbers.append([A, B])
res = 0

target = bin(K)[2:]
targets = [target]
while "10" in target:
    n = target.rfind("10")
    new_target = target[:n] + "0" + "1"*(len(target)-n-1)
    targets.append(new_target)
    target = new_target

targets = list(map(int, targets, [2]*len(targets)))

for target in targets:
    tmp = 0
    for a, b in numbers:
        if (target | a) == target:
            tmp += b
    res = max(res, tmp)
print(res)

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import copy

N, K = list(map(int, sys.stdin.readline().rstrip().split()))
data = []
for _ in range(N):
    A, B = list(map(int, sys.stdin.readline().rstrip().split()))
    data.append([A, B])

ans = 0


def lower(x, y):
    if(x > y):
        return False
    # print(bin(x), bin(y), bin(x|y), bin((x | y) ^ y))
    if((x | y) ^ y) == 0:
        return True
    else:
        return False


Nstr = list(reversed(bin(K)[2:]))
subNs = [K]
for i in range(len(Nstr)):
    if Nstr[i] == "0":
        continue
    subNstr = copy.deepcopy(Nstr)
    subNstr[i] = "0"
    for j in range(i):
        subNstr[j] = "1"

    realstr = ""
    for s in reversed(subNstr):
        realstr += s
    subNs.append(int(realstr, 2))


for subNstr in subNs:
    subans = 0
    for A, B in data:
        # print(A, subNstr, lower(A, subNstr))
        if(lower(A, subNstr)):
            subans += B
    # print(subNstr, subans)
    ans = max(subans, ans)

print(ans)

exit(0)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=[]
b=[]
for i in range(n):
    ia,ib=map(int,input().split())
    a.append(ia)
    b.append(ib)
bit=0
while k>=(1<<bit):
    bit+=1
ret=0
for i in range(n):
    if k==k|a[i]:
        ret+=b[i]
for i in range(bit):
    if k&(1<<i):
        mask=((1<<bit)-1)^((1<<(i+1))-1)
        ok=(k&mask)|((1<<i)-1)
        tmp=0
        for j in range(n):
            if ok==ok|a[j]:
                tmp+=b[j]
        ret=max(ret,tmp)
print(ret)

Submission status: Accepted

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

bs = str(bin(K))[2:]
for i in range(len(bs) - 1):
    if bs[i] == '1':
        a = len(bs) - 1 - i
        mask = K - (1 << a)
        mask |= ((1 << a) - 1)
        masks.append(mask)

anss = [0 for i in range(len(masks))]
for i in range(N):
    a,b = map(int,input().split())
    for i,m in enumerate(masks):
        if (m | a) == m:
            anss[i] += b

print(max(anss))

Submission status: Accepted

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


K_2 = bin(K)[2:]
max_kouho = [K_2,("1"* (len(K_2) -1) if len(K_2)>1 else "0") ]



for i in range(1,len(K_2)-1):
    if K_2[i] == "1"  and K_2.find("0") >-1:
        max_kouho.append(
            (K_2[:i]+"0"+ ("1" * 100) )[:len(K_2)] )
#print(max_kouho)

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

if K==0:
    ans =0
    for a,b in (AB):
        if a==0:
            ans +=b
    print(ans)
    exit()
dp = {key:0 for key in max_kouho}
for a,b in AB:
    #use
    for key in max_kouho:
        if int(key,2) |a ==int(key,2):
            dp[key]+=b
    #print(bin(a),b,dp)

print(max(dp[key] for key in max_kouho ))

Submission status: Accepted

Solution code:
from collections import defaultdict


def solve():
    n, k = map(int, input().split())
    d = defaultdict(int)
    for a, b in (map(int, input().split()) for _ in range(n)):
        d[a] += b
    bk = bin(k)[2:]
    lbk = len(bk)
    e = {k: 0}
    for i, c in enumerate(bk):
        if c == '1':
            e[int(bk[:i] + '0' + '1' * (lbk - i - 1), 2)] = 0

    for a, b in d.items():
        for c in e:
            if a | c == c:
                e[c] += b
    return max(e.values())


print(solve())

Submission status: Accepted

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

items = list(tuple(map(int,input().split())) for _ in range(N))

l = K.bit_length()

def it():

  for i in range(l):
    if K & (1 << i):
      j = (K-(1<<i))|((1<<i)-1)
      j = ~j
      yield sum(b for a,b in items if a&j==0)
  j = ~K
  yield sum(b for a,b in items if a&j==0)

print(max(it()))

Submission status: Accepted

Solution code:
# coding: utf-8

import math
import fractions
import heapq
import collections
import re
import array
import bisect

from collections import Counter, defaultdict


def array2d(dim1, dim2, init=None):
    return [[init for _ in range(dim2)] for _ in range(dim1)]


def main():
    N, K = map(int, input().split(" "))
    ks = format(K, "b")
    masks = [K]
    for i in range(len(ks)):
        if ks[-i-1] == "1":
            nks = ks[:-i-1] + "0" + "1" * i
            masks.append(int(nks, 2))
    l = len(masks)
    vs = [0] * l
    for _ in range(N):
        a, b = map(int, input().split())
        for i in range(l):
            if a & masks[i] == a:
                vs[i] += b
    return max(vs)


if __name__ == "__main__":
    print(main())