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:
N,K,*X = map(int,open(0).read().split())
S = bin(K)[2:]
L = len(S)
ls = [(a,b) for a,b in zip(*[iter(X)]*2)]
s = '0'
ans = 0
for i,c in enumerate(S):
  if c=='0':
    s += c
    continue
  j = L-i
  m = (1<<(j-1))-1
  n = int(s,2)<<j
  x = m|n
  v = 0
  for a,b in ls:
    if x==x|a:
      v += b
  ans = max(v,ans)
  s += c
v = 0
for a,b in ls:
  if K==K|a:
    v += b
ans = max(ans,v)
print(ans)

Submission status: Accepted

Solution code:
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, K = getlist()
	numL = []
	for i in range(N):
		A, B = getlist()
		numL.append([A, B])
	KK = K

	Kbit = []
	while True:
		Kbit.append(K % 2)
		K = int(K // 2)
		if K == 0:
			break

	Kbit = Kbit[::-1]
	M = len(Kbit)
	Ksum = [0] * M
	if Kbit[0] == 1:
		Ksum[0] = 2 ** (M - 1)
	for i in range(1, M):
		if Kbit[i] == 1:
			Ksum[i] = Ksum[i - 1] + 2 ** (M - 1 - i)
		else:
			Ksum[i] = Ksum[i - 1]

	# print(Kbit)
	# print(Ksum)

	ans = 0
	for i in range(1, M - 1):
		if Kbit[i] == 1:
			var = Ksum[i - 1] + 2 ** (M - 1 - i) - 1
			cnt = 0
			for j in range(N):
				A = numL[j][0]
				B = numL[j][1]
				if var | A == var:
					cnt += B

			ans = max(ans , cnt)

	cnt = 0
	for i in range(N):
		A = numL[i][0]
		B = numL[i][1]
		if (2 ** (M - 1) - 1) | A == (2 ** (M - 1) - 1):
			cnt += B
	ans = max(ans, cnt)
	cnt = 0
	for i in range(N):
		A = numL[i][0]
		B = numL[i][1]
		if KK | A == KK:
			cnt += B
	ans = max(ans, cnt)

	print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

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)]
    if K == 0:
        ans = 0
        for a,b in number:
            if a == 0:
                ans += b
        print(ans)
        return 

    msb = 30
    while (K>>msb)&1 == 0:
        msb -= 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: Accepted

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

def solve(k):
  res = 0
  for a, b in AB:
    if a | k <= k:
      res += b
  return res

ans = solve(K)
while K:
  bottom1 = K & -K
  k = (K ^ bottom1) + (bottom1 - 1)
  ans = max(ans, solve(k))
  K ^= bottom1

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

# Kを二進数表記する
# Kでbit=1の桁でbit orを0にすると，それ以下の桁は何でもよい

N,K = LI()
A0,B0 = LIR(N,2)

A = []
B = []
for i in range(N):
    if A0[i] <= K:
        A.append(A0[i])
        B.append(B0[i])

Ks = format(K,'b')
L = len(Ks)
last_zero = -1
for i in range(L)[::-1]:
    if Ks[i] == '0':
        last_zero = i
        break

if last_zero == -1:
    print(sum(B))
else:
    zeros = []
    must_zero = []
    for i,s in enumerate(Ks):
        if s == '1':
            must_zero.append(zeros+[i])
        else:
            zeros.append(i)
            if i == last_zero:
                must_zero.append(zeros)
                break
    ans = 0
    for zl in must_zero:
        temp = 0
        for a,b in zip(A,B):
            flag = False
            for i in zl:
                if a & 1<<(L-i-1) != 0:
                    flag = True
                    break
            if not flag:
                temp += b
        if temp > ans:
            ans = temp
    print(ans)

Submission status: Accepted

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

n, k = map(int,input().split())
A = [list(map(int,input().split())) for i in range(n)]
l = 32
bk = format(k, "b").zfill(l)
B = [k]
nk = 0
for i in range(l):
    if bk[i] == "1":
        nk += 2**(l-1-i)
        B.append(nk - 1)

# for i in range(len(B)):
#     print(format(B[i], "b").zfill(l))

ans0 = 0
for i in range(len(B)):
    ans = 0
    for j in range(n):
        if B[i] | A[j][0] == B[i]:
            ans += A[j][1]
    ans0 = max(ans0, ans)
print(ans0)

Submission status: Accepted

Solution code:
N,K,*X = map(int, open(0).read().split())
S = bin(K)[2:]
L = len(S)
one = set()
ls = [(a,b) for a,b in zip(*[iter(X)]*2) if a<=K]
kls = [K]
ans = 0
for i in range(L):
  if S[i]=='1':
    m = int(S[:i]+'0'+'1'*(L-i-1),2)
    kls.append(m)
for k in kls:
  m = 0
  for a,b in ls:
    if k==k|a:
      m += b
  ans = max(ans,m)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7



n, k = LI()
AB = LIR(n)

def count(d):
    ret = 0
    for a, b in AB:
        if not ~d & a:
            ret += b
    return ret

ans = count(k)
for i in range(k.bit_length()):
    if k >> i & 1:
        ans = max(ans, count(((k >> i) << i) - 1))

print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
AB = np.array([lr() for _ in range(N)], dtype=np.int64)
A = AB[:, 0]
B = AB[:, 1]
answer = 0

def F(x):
    global answer
    #bitごとで全てxに含まれる
    index = np.where((A|x) <= x)[0]
    if index is not None:
        if np.sum(B[index]) > answer:
            answer = B[index].sum()

cur = 0
F(K)
for i in range(K.bit_length()-1, -1, -1):
    if (((1 << i) & K) >> i) & 1:
        F(cur + ((1<<i) - 1))
        cur += (1<<i)

print(answer)
# 06

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=[list(map(int,input().split()))for i in range(n)]
p=0
for i in range(31):
    c=1
    if i!=0:
        if k|(2**i)==k:
            k-=2**i
            k=k|(2**i-1)
        else:
            c=0
    if c:
        q=0
        for j,h in s:
            if k|j==k:
                q+=h
        p=max(p,q)
print(p)

Submission status: Accepted

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

Solution code:
N,K=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N)]
dp=[0]*31
for a,b in AB:
    x=1
    for i in range(30):
        if K&x and ((K-x)|(x-1))&a==a:
            dp[i]+=b
        x<<=1
    if K&a==a:
        dp[-1]+=b
print(max(dp))

Submission status: Accepted

Solution code:
#02:02
n,k = map(int,input().split())
judge = [k]
for d in range(30):
  kx = k // 2**d * 2**d
  if kx != 0:
    judge.append(kx)
  else:
    break
l = len(judge)
for i in range(1,l):
  judge[i] -= 1
judge.reverse()
#print(judge)
can = [0 for _ in range(l)]
for _ in range(n):
  a,b = map(int,input().split())
  for i in range(l):
    if a | judge[i] == judge[i]:
      #print(bin(a),bin(judge[i]))
      can[i] += b
  #print(can)
#print(can)
print(max(can))

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a, b = [0] * n, [0] * n
for i in range(n):
    a[i], b[i] = map(int, input().split())
ans = 0
z = list(zip(a, b))
for x, y in z:
    if (k | x) == k:
        ans += y
for i in range(30):
    if (k >> i) & 1:
        res = 0
        t = ((k >> (i + 1)) << (i + 1)) + (1 << i) - 1
        for x, y in z:
            if (t | x) == t:
                res += y
        ans = max(ans, res)
print(ans)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,K=MI()
    K_bin = bin(K)[2:]
    AB=LLIN(N)

    ans = 0
    for a,b in AB:
        if a&K==a:
            ans += b

    for i in range(len(K_bin)):
        if K_bin[i]=="0":
            continue
        i_inv = len(K_bin)-(i+1)
        res = 0
        k = K - (1<<i_inv)
        for a,b in AB:
            left_a = (a>>i_inv<<i_inv) #上位i+1bit            
            if left_a&k==left_a:
                res += b
            else:
                continue
        ans = max(ans, res)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,K=MI()
    K_bin = bin(K)[2:]
    AB=LLIN(N)

    ans = 0
    for a,b in AB:
        if a&K==a:
            ans += b

    for i in range(len(K_bin)):
        if K_bin[i]=="0":
            continue
        i_inv = len(K_bin)-(i+1)
        res = 0
        # print(i)
        # print(bin(K)[2:], bin(1<<i_inv)[2:])
        k = K - (1<<i_inv)
        for a,b in AB:
            left_a = (a>>i_inv<<i_inv) #上位i+1bit            
            # print(bin(a)[2:],bin(left_a)[2:])
            if left_a&k==left_a:
                res += b
            else:
                continue
        ans = max(ans, res)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N, K = (int(i) for i in input().split())
    AB = [[int(i) for i in input().split()] for j in range(N)]
    K_bi = str(bin(K))[2:]
    M = len(K_bi)
    posi = []
    for i in range(M-1):
        if K_bi[i] == "1":
            posi.append(i)
    ans = 0
    for i in posi:
        cur_bit = int(K_bi[:i] + "0" + "1" * (M - (i + 1)), 2)
        cur_s = 0
        for a, b in AB:
            if a | cur_bit == cur_bit:
                cur_s += b
        ans = max(ans, cur_s)
    cur_s = 0
    for a, b in AB:
        if a | K == K:
            cur_s += b
    ans = max(ans, cur_s)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

n, k = map(int, input().split())
m = map(int, read().split())
AB = list(zip(m, m))
k_bin = bin(k)[2:]
l = len(k_bin)
def count(d):
  s = 0
  for a, b in AB:
    if a & ~d:
      continue
    s += b
  return s

ans = count(k)
for i in range(l):
  if (k >> i) & 1:
    d = ((k >> i) << i) - 1
    temp = count(d)
    ans = max(ans, temp)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
a = [list(map(int,input().split())) for i in range(n)]
ans = [0]
l = max(k.bit_length(),1)
for i in range(l-1,-1,-1):
  if i == 0:
    x = k
  elif k & 1 << i:
    x = (k >> (i+1)) << i+1 | (1 << i)-1
  sm = 0
  for j in range(n):
    if a[j][0] | x == x:
      sm += a[j][1]
  ans.append(sm)
print(max(ans))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
a = []
for _ in range(N):
  u, v = map(int, input().split())
  a.append((u, v))
b = bin(K)[2: ]
t = [K]
for i in range(len(b)):
  if b[i] == "1":
    tt = 0
    for j in range(i):
      if b[j] == "1": tt += 1 << (len(b) - j - 1)
    for j in range(i + 1, len(b)):
      tt += 1 << (len(b) - j - 1)
    t.append(tt)
res = 0
for tt in t:
  ttt = 0
  for i in range(N):
    u, v = a[i]
    if tt & u == u:
      ttt += v
  res = max(res, ttt)
print(res)

Submission status: Accepted

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

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, -2, -1):
        mask = K
        if i > -1:
            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: Accepted

Solution code:
from collections import Counter

N, K, *AB = map(int, open(0).read().split())

C = Counter()
for a, b in zip(*[iter(AB)] * 2):
    C[a] += b

ma = sum(v for k, v in C.items() if k | K == K)

S = list(bin(K)[2:])
i = -1
for _ in range(S.count('1')):
    T = S[:]
    i = T.index('1', i + 1)
    T[i:] = "0" + "1" * (len(T) - i - 1)

    T = int("".join(T), 2)
    ma = max(ma, sum(v for k, v in C.items() if k | T == T))

print(ma)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n, k = LI()
    ab = LIR(n)
    def f(k):
        res = 0
        for a, b in ab:
            if k & a == a:
                res += b
        return res
    ans = f(k)
    for i in range(31):
        i1 = (1 << i)
        if k & i1:
            K = (k | (i1 - 1)) ^ i1
            res = f(K)
            if ans < res:
                ans = res
    print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n, k = LI()
    ab = LIR(n)
    ans = 0
    for a, b in ab:
        if k & a == a:
            ans += b
    for i in range(31):
        if k & (1 << i):
            res = 0
            K = (k | ((1 << i) - 1)) ^ (1 << i)
            for a, b in ab:
                if K & a == a:
                    res += b
            if ans < res:
                ans = res
    print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

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

bs = {K: 0}
x = K
while x:
    bs[x - 1] = 0  # x-1:xの最下位bitを消して、その下位bitをすべて立てたもの
    x -= x & (-x)  # 最下位bitを消していく
    # https://atcoder.jp/contests/tenka1-2017/submissions/6793509

for _ in range(N):
    num, value = map(int, input().split())
    for b in bs:
        if (b | num) == b:  # orでmaskに別のbitが立たないなら加算
            bs[b] += value

print(max(bs.values()))

Submission status: Accepted

Solution code:
# 解説を見た
# https://atcoder.jp/contests/tenka1-2017/submissions/1640474

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

bs = {K: 0}
for j in range(K.bit_length()):
    if K & (1 << j) > 0:
        bs[K & ~(1 << j) | ((1 << j) - 1)] = 0
        # Kで立っているbitを消して、下位bitをすべて立てたもの

for _ in range(N):
    num, value = map(int, input().split())
    for b in bs:
        if (b | num) == b:
            bs[b] += value

print(max(bs.values()))

# 累積orで桁繰上りはない
# 二進表記の各桁でbitを立てるかどうかを決めたら、それを満たすように貪欲に整数を買う
# 調べるbitの候補は
# K自身と途中の1を0にして、その下位をすべて1にしたもの
# となり、総数はKの二進表記の桁数になる
# 各候補についてO(N)で貪欲に求まるので、O(30*N)くらい

Submission status: Accepted

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

AB = []

for i in range(N):

    a,b = map(int,input().split())
    AB.append([a,b,format(a,'b')])

kb = format(K,'b')
#print (kb)
ans = 0

for i in range(len(kb)):

    now = 0
    if kb[-1-i] == "1":

        for j in range(N):

            flag = True
            at = AB[j][2]

            if len(kb) < len(at):
                continue

            for m in range(len(at)):

                

                if m == i and at[-1-m] == "1":
                    flag = False
                    break

                elif m > i and kb[-1-m] == "0" and at[-1-m] == "1":
                    flag = False
                    break

            if flag:
                now += AB[j][1]

        #print (i,now)
        ans = max(ans,now)
        
print (ans)

Submission status: Accepted

Solution code:
import copy
N,K=map(int,input().split())
L=[]
for i in range(N):
    a,b=map(int,input().split())
    if a<=K:
        L.append([a,b])

#print(L)
k=[]
num=copy.deepcopy(K)
for i in range(30):
    if num//(2**(29-i))==1:
        k.append(1)
        num%=(2**(29-i))
    else:
        k.append(0)
        num%=(2**(29-i))
        
ans=0
for a,b in L:
    if K|a==K:
        ans+=b
NUM=0
for i in range(30):
    if k[i]==1:
        cnt=0
        NUM+=2**(29-i)
        for a,b in L:
            if K-2**(29-i)|a<NUM:
                cnt+=b
        if ans<cnt:
            ans=cnt
        #print(cnt,i,K-2**(29-i))
    
print(ans)
#print(k)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,k=map(int,input().split())
    k+=1
    AB=[tuple(map(int,input().split())) for _ in range(n)]

    dp=[0]*35 # dp[d]: less than が確定するのが d 桁目のときの最大値
    # dp[d] の状態のものが a を買えるのは、d 以上の桁については ad<=kd かつ、
    # d 桁目については ad<kd となるもののみ
    for a,b in AB:
        for d in range(34,-1,-1):
            kd=(k>>d)&1
            ad=(a>>d)&1
            if(ad>kd): break
            if(ad<kd):
                dp[d]=dp[d]+b

    print(max(dp))
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,k=map(int,input().split())
    k+=1
    AB=[tuple(map(int,input().split())) for _ in range(n)]

    dp=[0]*35 # dp[d]: less than が確定するのが d 桁目のときの最大値
    # dp[d] の状態のものが a を買えるのは、d 以上の桁については ad<=kd かつ、
    # d 桁目については ad<kd となるもののみ
    for a,b in AB:
        ndp=dp[:]
        for d in range(34,-1,-1):
            kd=(k>>d)&1
            ad=(a>>d)&1
            if(ad>kd): break
            if(ad<kd):
                ndp[d]=dp[d]+b
        dp=ndp

    print(max(dp))
resolve()

Submission status: Accepted

Solution code:
def main():
    m=30
    n,k=map(int,input().split())
    ab=[list(map(int,input().split())) for _ in [0]*n]
    test=[k]
    k=(("0"*m)+(bin(k)[2:]))[-m:]
    for i in range(m):
        if k[i]=="1":
            test.append(int(k[:i]+"0"+"1"*(m-i-1),2))
    m=0
    for t in test:
        cnt=0
        for a,b in ab:
            if a|t==t:
                cnt+=b
        m=max(cnt,m)
    print(m)
main()

Submission status: Accepted

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 l:
        p |= (1<<i)-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: Accepted

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

ret = 0
for A, B in AB :
    if A & ~K == 0 :
        ret += B
        
for i in range(30) :
    if K & (1 << i) == 0 :
        continue
        
    k = K
    k ^= 1 << i
    k |= (1 << i) - 1
    s = 0
    for A, B in AB :
        if A & ~k == 0 :
            s += B
            
    ret = max(ret, s)
    
print(ret)

Submission status: Accepted

Solution code:
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = list(map(int, sys.stdin.readline().split()))
A, B = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N)]))

A = np.array(A, dtype=int)
B = np.array(B, dtype=int)

ans = B[np.bitwise_or(A, K) == K].sum()
for i in range(1, K.bit_length() + 1):
    if K >> i & 1:
        k = (K - (1 << i)) | ((1 << i) - 1)
        # print(np.binary_repr(K, 10))
        # print(np.binary_repr(k, 10))
        ans = max(ans, B[np.bitwise_or(A, k) == k].sum())
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)]

L = len(bin(K))-2

ans = 0
for a, b in AB:
    if (K | a) == K:
        ans += b

for n in reversed(range(L)):
    if (1 << n) & K:
        score = 0
        mask = (((1<<L)-(1<<n)) & K) - 1
        for a, b in AB:
            if (mask | a) == mask:
                score += b
        ans = max(ans, score)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools

import queue
from collections import deque



def main():
    num, k = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(num)]

    ans_dic = defaultdict()
    ans_dic[k] = 0

    bin_data = list(bin(k)[2:])
    for i in range(len(bin_data)):
        if bin_data[i] == '1':
            new_data = bin_data[:i] + ['0'] + ['1' for j in range(len(bin_data) - i - 1)]
            now_str = ''.join(new_data)
            now_int = int(now_str, 2)
            ans_dic[now_int] = 0

    # print(ans_dic)


    for i in range(num):
        a, b = data[i]
        for key in ans_dic.keys():
            if key | a == key:
                ans_dic[key] += b

    ans = max(list(ans_dic.values()))
    print(ans)




if __name__ == '__main__':
    main()
    # test()