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: Time Limit Exceeded

Solution code:
def inpl(): return [int(i) for i in input().split()]
N, K = inpl()
H = {0: 0}
for i in range(N):
    a, b= inpl()
    for ia, ib in H.copy().items():
        if ia | a <= K or (ia == 0 and a <= K):
            H[ia|a] = max(H.get(ia|a, 0), ib+b)
print(max(H.values()))

Submission status: Time Limit Exceeded

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

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
    for a,b in ab:
        bina = bin(a)[2:].zfill(binn)
        lt = True
        
        for digitc, digita in zip(cand, bina):
            if digita > digitc:
                lt = False
                
        if lt:
            tmp += b
                
    ans = max(ans, tmp)
    
print(ans)

Submission status: Time Limit Exceeded

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()))
    # print(A)
    # print(bin(A)[2:])
    data.append([list(reversed(bin(A)[2:])), B])

ans = 0


def lower(x, y):
    if(len(x) > len(y)):
        return False
    for xx, yy in zip(x, y):
        if (xx == "1" and yy == "0"):
            return False
    else:
        return True


Nstr = list(reversed(bin(K)[2:]))
subNstrs = [Nstr]
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"
    subNstrs.append(subNstr)


for subNstr in subNstrs:
    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: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from numpy import bitwise_or
from bisect import bisect, insort

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 bitwise_or(target, a) == target:
            tmp += b
    res = max(res, tmp)
print(res)

Submission status: Time Limit Exceeded

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)
dp={0:0}
for i in range(n):
    dp2={}
    for key,val in dp.items():
        dp2[key]=val
    for key,val in dp.items():
        nk=(key|a[i])
        if nk<=k:
            if nk in dp:
                dp2[nk]=max(dp2[nk],val+b[i])
            else:
                dp2[nk]=val+b[i]
    for key,val in dp2.items():
        dp[key]=val
ret=0
for val in dp.values():
    ret=max(ret,val)
print(ret)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, k = list(map(int, input().split()))
    a = []
    b = []
    for _ in range(n):
        cur_a, cur_b = list(map(int, input().split()))
        a.append(cur_a)
        b.append(cur_b)
    print(rec(a, b, 0, 0, k))

def rec(a, b, bitor, value, k):
    if k < bitor:
        return -1
    if len(a) == 0:
        return value
    else:
        return max(rec(a[1:], b[1:], bitor | a[0], value+b[0], k), rec(a[1:], b[1:], bitor, value, k))

main()

Submission status: Accepted

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

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

Submission status: Accepted

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

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

# 桁DPのような形で、KをMAX数十パターン試す
# Kが1010101のとき
# K= 1010101, 1010011, 1001111, 0111111をためせばよい。
# 1を0に置き換えて、あとは1連発。
# 値は貪欲にとってよい。論理和をとって変化しなければOK
# 6 | 2 == 6 -> True, 6 | 3 == 6 -> False
def solve(X):
  res = 0
  for a,b in ITEM:
    if a | X == X:
      res += b
  #print(X,res)
  return res

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

Submission status: Accepted

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

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

ans = 0

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
import numpy as np
import decimal
import collections
import itertools
import sys
#Union-Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = [-1 for i in range(self.n)]
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def unite(self, x, y):
        p = self.find(x)
        q = self.find(y)
        if p == q:
            return None
        if p > q:
            p, q = q, p
        self.par[p] += self.par[q]
        self.par[q] = p
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def size(self, x):
        return -self.par[self.find(x)]

#素数関連
def prime_numbers(x):
    if x < 2:
        return []
    prime_numbers = [i for i in range(x)]
    prime_numbers[1] = 0
    for prime_number in prime_numbers:
        if prime_number > math.sqrt(x):
            break
        if prime_number == 0:
            continue
        for composite_number in range(2 * prime_number, x, prime_number):
            prime_numbers[composite_number] = 0
    return [prime_number for prime_number in prime_numbers if prime_number != 0]
def is_prime(x):
    if x < 2:
        return False
    if x == 2 or x == 3 or x == 5:
        return True
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0:
        return False
    prime_number = 7
    difference = 4
    while prime_number <= math.sqrt(x):
        if x % prime_number == 0:
            return False
        prime_number += difference
        difference = 6 - difference
    return True
#nCr
mod = 10 ** 9 + 7
class nCr():
    def __init__(self, n):
        self.n = n
        self.fa = [1] * (self.n + 1)
        self.fi = [1] * (self.n + 1)
        for i in range(1, self.n + 1):
            self.fa[i] = self.fa[i - 1] * i % mod
            self.fi[i] = pow(self.fa[i], mod - 2, mod)
    def comb(self, n, r):
        if n < r:return 0
        if n < 0 or r < 0:return 0
        return self.fa[n] * self.fi[r] % mod * self.fi[n - r] % mod
#BIT
class BinaryIndexedTree():
    def __init__(self, n):
        self.n = n
        self.BIT = [0] * (self.n + 1)
    def add(self, i, x):
        while i <= self.n:
            self.BIT[i] += x
            i += i & -i
    def query(self, i):
        res = 0
        while i > 0:
            res += self.BIT[i]
            i -= i & -i
        return res
#Associative Array
class AssociativeArray():
    def __init__(self, q):
        self.dic = dict()
        self.q = q
    def solve(self):
        for i in range(self.q):
            Query = list(map(int, input().split()))
            if Query[0] == 0:
                x, y, z = Query
                self.dic[y] = z
            else:
                x, y = Query
                if y in self.dic:
                    print(self.dic[y])
                else:
                    print(0)
#Floor Sum
def floor_sum(n, m, a, b):
    res = 0
    if a >= m:
        res += (n - 1) * n * (a // m) // 2
        a %= m
    if b >= m:
        res += n * (b // m)
        b %= m
    y_max = (a * n + b) // m
    x_max = y_max * m - b
    if y_max == 0:
        return res
    res += y_max * (n + (-x_max // a))
    res += floor_sum(y_max, a, m, (a - x_max % a) % a)
    return res
#Z-Algorithm
def z_algorithm(s):
    str_len = len(s)
    res = [0] * str_len
    res[str_len - 1] = str_len
    i, j = 1, 0
    while i < str_len:
        while i + j < str_len and s[i + j] == s[j]:
            j += 1
        res[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < str_len and j > res[k] + k:
            res[i + k] = res[k]
            k += 1
        i += k
        j -= k
    return res
class Manacher():
    def __init__(self, s):
        self.s = s
    def coustruct(self):
        i, j = 0, 0 
        s_len = len(s)
        res = [0] * s_len
        while i < s_len:
            while i - j >= 0 and i + j < s_len and s[i - j] == s[i + j]:
                j += 1
            res[i] = j
            k = 1
            while i - k >= 0 and k + res[i - k] < j:
                k += 1
            i += k
            j -= k
n, k = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n)]
ans = 0
for i in ab:
    if i[0] | k == k:
        ans += i[1]
cur = 0
for i in range(len(bin(k)) + 1)[::-1]:
    if k & (1 << i) > 0:
        cur += (1 << i) - 1
        cnt = 0
        for j in ab:
            if j[0] | cur <= k:
                cnt += j[1]
        ans = max(ans, cnt)
        cur += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict


def main():
    N, K = map(int, input().split())
    integers = [list(map(int, input().split())) for _ in range(N)]
    # bitwise orの結果の候補を計算
    len_bin_k = len('{:b}'.format(K))
    keys = [K]
    for shift in range(1, len_bin_k + 1):
        if (K >> shift) & 1 == 1:
            # 右からshift bit目が0で、それより右が全部1の数
            # （例）K:1100101、shift:3 => 1100011
            keys.append(((K >> shift) << shift) - 1)
    vals = defaultdict(int)
    for a, b in integers:
        for k in keys:
            # bitwise orの結果を変えない整数の場合は価値を合算
            if k | a == k:
                vals[k] += b
    if len(vals.values()) == 0:
        print(0)
    else:
        print(max(vals.values()))


if __name__ == '__main__':
    main()

Submission status: Accepted

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


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

AB = []

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

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

ANS = [0]*k  # 

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

print(max(ANS))

Submission status: Accepted

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

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

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

print(max(values.values()))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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

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

print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

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

# そのままの　ｋ
ans = 0
for a, b in ab:
    if k & a == a:
        ans += b

for i in range(31):
    # 上からi桁目までいっち、あとは1111
    if k >> i & 1 == 0:
        continue
    nk = k
    nk &= ~(1 << i)
    for j in range(i - 1, -1, -1):
        nk |= 1 << j

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

Submission status: Accepted

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 = [K]
for i in range(30):
    if K[i]=="1":
        x = K[:i]+"0"+"1"*(30-i-1)
        F.append(x)
G = []
for f in F:
    g = []
    for i in range(30):
        if f[i]=="0":
            g.append(i)
    G.append(g)
cmax = 0
for g in G:
    cnt = 0
    for i in range(N):
        a = A[i]
        flag = 0
        for j in g:
            if a[j]!="0":
                flag = 1
                break
        if flag==0:
            cnt += X[i][1]
    cmax = max(cmax,cnt)
print(cmax)

Submission status: Accepted

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(K)

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

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

Submission status: Accepted

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

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

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

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

# print(k_bits)

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

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

# bits_cands = []
# print(max_bit)
# curr = [1]
# for i in range(max_bit-1,-1,-1):
#     if k%(1<<i) == 0:
#         curr.append(0)
#         row = curr + []

Submission status: Accepted

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

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

ans=0
ab.sort()
m=bin(k)
# print(m)
klst=[m]
for i in range(2,len(m)):
    if m[i]=="1":
        klst.append(m[:i]+"0"+"1"*(len(m)-i-1))
for i in range(len(klst)):
    klst[i]=int(klst[i],0)
# print(klst)
for i in klst:
    tmp=0
    for j in range(n):
        a,b=ab[j]
        if a|i==i:
            tmp+=b
    ans=max(ans,tmp)
print(ans)

Submission status: Accepted

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

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

ans=0
ab.sort()
m=bin(k)
# print(m)
klst=[m]
for i in range(2,len(m)):
    if m[i]=="1":
        klst.append(m[:i]+"0"+"1"*(len(m)-i-1))

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

Submission status: Accepted

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


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

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


if __name__ == "__main__":
    solve()

Submission status: Accepted

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

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

Submission status: Accepted

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


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


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


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


if __name__ == "__main__":
    solve()

Submission status: Accepted

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


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


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

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


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


if __name__ == "__main__":
    solve()

Submission status: Accepted

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

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

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

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

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

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==0)
for i in range(30):
    if K>>i&1:
        k = (K^1<<i)|(1<<i)-1
        ans = max(ans, sum(b for a, b in AB if a&~k==0))
print(ans)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

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

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

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = map(int, input().split())
a = [None]*n
b = [None]*n
for i in range(n):
    a[i],b[i] = map(int, input().split())

l = k.bit_length()
def sub(k):
    ans = 0
    for num,val in zip(a,b):
        if (k|num) == k:
            ans += val
    return ans
ans = sub(k)
for i in range(l):
    # i桁が1のとき、そこを0にしてそれ以降を1にする
    if k>>i&1:
        kk = ((k>>i)-1)*(1<<i) + (1<<i) - 1
        val = sub(kk)
        ans = max(ans, val)

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.readline

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
def II(): return int(input())
def ILI(): return list(map(int, input().split()))


def read():
    N, K = ILI()
    A, B = [], []
    for __ in range(N):
        a, b = ILI()
        A.append(a)
        B.append(b)
    return N, K, A, B


def solve(N, K, A, B):
    l_K = [K]
    len_bin_K = len(bin(K)) - 2
    all_1 = sum([2 ** x for x in range(len_bin_K - 1)])
    l_K.append(all_1)
    for i in range(len(bin(K)) - 4, -1, -1):
        if K >> i & 1 == 1:
            now = K >> i
            now = now & ~1
            now = ~now
            now = now << (i)
            now = ~now
            l_K.append(now)

    l_ans = [0] * len(l_K)
    for i in range(N):
        for j in range(len(l_K)):
            if l_K[j] | A[i] == l_K[j]:
                l_ans[j] += B[i]
    ans = max(l_ans)
    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

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

print(ans)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

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