Problem:


Score : 500 points

Problem Statement

Seisu-ya, a store specializing in non-negative integers, sells N non-negative integers. The i-th integer is A_i and has a utility of B_i.
There may be multiple equal integers with different utilities.

Takahashi will buy some integers in this store. He can buy a combination of integers whose bitwise OR is less than or equal to K. He wants the sum of utilities of purchased integers to be as large as possible.

Find the maximum possible sum of utilities of purchased integers.

Constraints

1 \leq N \leq 10^5

0 \leq K < 2^{30}

0 \leq A_i < 2^{30}(1\leq i\leq N)

1 \leq B_i \leq 10^9(1\leq i\leq N)

All input values are integers.

Inputs

Input is given from Standard Input in the following format:

N K
A_1 B_1
:
A_N B_N

Outputs

Print the maximum possible sum of utilities of purchased integers.

Sample Input 1

3 5
3 3
4 4
2 5

Sample Output 1

8

Buy 2 and 3 to achieve the maximum possible total utility, 8.

Sample Input 2

3 6
3 3
4 4
2 5

Sample Output 2

9

Buy 2 and 4 to achieve the maximum possible total utility, 9.

Sample Input 3

7 14
10 5
7 4
11 4
9 8
3 6
6 2
8 9

Sample Output 3

32



Sample input:
3 5
3 3
4 4
2 5


Sample output:
8

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
AB = []
for _ in range(N) :
    A, B = map(int, input().split())
    if A <= K :
        AB.append((A, B))

if bin(K)[2:].count('0') == 0 :
    print(sum(B for A, B in AB))
else :
    M = (1 << (len(bin(K)) - 2)) - 1
    ret = 0
    for i in range(29, -1, -1) :
        if M ^ (1 << i) <= K :
            s = 0
            for A, B in AB :
                if not A & (1 << i) :
                    s += B
            ret = max(ret, s)
            
    print(ret)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
AB = []
for _ in range(N) :
    A, B = map(int, input().split())
    if A <= K :
        AB.append((A, B))

M = (1 << (len(bin(K)) - 2)) - 1
ret = 0
for i in range(29, -1, -1) :
    if M ^ (1 << i) <= K :
        s = 0
        for A, B in AB :
            if not A & (1 << i) :
                s += B
        ret = max(ret, s)
        
print(ret)

Submission status: Wrong Answer

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

    max_2 = 1
    while max_2 <= k:
        max_2 *= 2
    max_num = max_2 // 2
    max_2 -= 1

    while max_num != 0:
        if max_2 - max_num <= k:
            ans_dic[max_2 - max_num] = 0
            max_num //= 2
        else:
            break

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

Submission status: Wrong Answer

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

print(res)

Submission status: Wrong Answer

Solution code:

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

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

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

ans = 0
zeroidx = [i 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
    
L = len(K2)


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: Wrong Answer

Solution code:
N, K = map(int, input().split())
A, B = (
    zip(*(map(int, input().split()) for _ in range(N))) if N else
    ((), ())
)

# 桁DP
L = K.bit_length()
ans = max(
    sum(
        b
        for a, b in zip(A, B)
        if a.bit_length() <= L and all(
            (a >> (L - i - 1)) & 1 <= (K >> (L - i - 1)) & 1
            for i in range(k)
        ) and (k == L or ((a >> (L - k - 1)) & 1 == 0))
    )
    for k in range(L + 1)
)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,k=map(int,input().split())
kk=k.bit_length()
A=[0]*k.bit_length()
for i in range(n):
  a,b=map(int,input().split())
  if a<=k:
    aa=str(bin(a))[2:].zfill(kk)
    for j in range(kk):
      if aa[j]=="0":
        A[j]+=b
ans=0
for i in range(kk):
  if int("1"*i+"0"+"1"*(kk-i-1),2)<=k:
    ans=max(ans,A[i])
print(ans)

Submission status: Wrong Answer

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)
    for A, B in ABs:
        if A < C and A & (1<<i) == 0:
            v += B
    ans = max(ans, v)

print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
d = 31
z = [list(map(int, input().split())) for _ in range(n)]
used = [True] * 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 == 0:
			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: Wrong Answer

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

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

if k == 0:
    ans = 0
    for a, b in ab:
        if a == 0:
            ans += b
    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: Wrong Answer

Solution code:
n, k = map(int, input().split())
in_list = []
for _ in range(n):
	m = tuple(map(int, input().split()))
	if m[0] < k:
		in_list.append(m)

ans = 0
i = 0
for e1 in reversed(in_list):
	base, val = e1[0], e1[1]
	cnt = 0
	for j in range(0, len(in_list)-i-1):
		e2 = in_list[j]
		if (base | e2[0]) <= k:
			val += e2[1]
			base = base | e2[0]
			cnt += 1
	if val > ans:
		ans = val
		ans_cnt = cnt
	i += 1
	if cnt > i:
		break
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, raw_input().split(' '))
kbin = bin(K)[2:]
klen = len(kbin) if K > 0 else 0

vs = [0]*31
vs2 = [0]*31
for n in xrange(N):
  a, b = map(int, raw_input().split(' '))
  alen = len(bin(a)[2:]) if a > 0 else 0
  for i in xrange(-klen-1, -alen):
    vs[i] += b
  if a <= (K % (2**alen)):
    vs2[-alen] += b

ans = [0]*30
tmp = 0
for i in xrange(-klen, 0):
  ans[i] += vs[i] + tmp
  if kbin[i] == '1':
    tmp += vs2[i]
ans.append(tmp+vs2[0])

print max(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, raw_input().split(' '))
kbin = bin(K)[2:]
klen = len(kbin)

vs = [0]*31
vs2 = [0]*31
for n in xrange(N):
  a, b = map(int, raw_input().split(' '))
  alen = len(bin(a)[2:]) if a > 0 else 0
  for i in xrange(-klen-1, -alen):
    vs[i] += b
  if a <= (K % (2**alen)):
    vs2[-alen] += b

ans = [0]*30
tmp = 0
for i in xrange(-klen, 0):
  ans[i] += vs[i] + tmp
  if kbin[i] == '1':
    tmp += vs2[i]
ans.append(tmp+vs2[0])

print max(ans)

Submission status: Wrong Answer

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]
# print(A)
L = K.bit_length()
ans = 0
for i in reversed(range(L)):
    bit = (1 << i) & K
    if bit != 1:
        # print(bit, ':', i)
        cand = 0
        bor = 0
        tmp_K = K & ~(1 << i) | ((1 << i) - 1)
        for a, b in A:
            if (a | tmp_K) <= K:
                # print(a, (a >> i) & 1)
                cand += b
                bor ^= a
        ans = max(ans, cand)
        assert(bor <= K)

print(ans)

Submission status: Wrong Answer

Solution code:
def read_stdin():
    n, k = map(int, input().split())
    p = []
    for i in range(n):
        a, b = map(int, input().split())
        if a <= k:
            p.append((a, b))
    n = len(p)
    return (n, k, p)


def main(n, k, p):
    max_score = 0
    if not p:
        print(0)
        exit()
    for i in range(n):
        if k | p[i][0] == k:
            max_score += p[i][1]

    mask = bin(k)[2:]
    bit_size = len(mask)
    for i in range(bit_size - 1):
        # if mask[i] == '1':
        rest = bit_size - i - 1
        k_alt = int(mask[:i] + '0' + ('1' * (bit_size - i - 1) if rest > 0 else ''), 2)
        score = 0
        for j in range(n):
            if k_alt | p[j][0] == k_alt:
                score += p[j][1]
        max_score = max(max_score, score)
    print(max_score)


if __name__ == '__main__':
    n, k, p = read_stdin()
    main(n, k, p)

Submission status: Wrong Answer

Solution code:
def read_stdin():
    n, k = map(int, input().split())
    p = []
    for i in range(n):
        a, b = map(int, input().split())
        p.append((a, b))
    return (n, k, p)


def main(n, k, p):
    max_score = 0
    for i in range(n):
        if k | p[i][0] == k:
            max_score += p[i][1]

    mask = bin(k)[2:]
    bit_size = len(mask)
    for i in range(bit_size - 1):
        # if mask[i] == '1':
        rest = bit_size - i - 1
        k_alt = int(mask[:i] + '0' + ('1' * (bit_size - i - 1) if rest > 0 else ''), 2)
        score = 0
        for j in range(n):
            if k_alt | p[j][0] == k_alt:
                score += p[j][1]
        max_score = max(max_score, score)
    print(max_score)


if __name__ == '__main__':
    n, k, p = read_stdin()
    main(n, k, p)

Submission status: Wrong Answer

Solution code:
N, K = map(int, raw_input().split(' '))
kbin = bin(K)[2:]
klen = len(kbin)

vs = [0]*31
vs2 = [0]*31
for n in xrange(N):
  a, b = map(int, raw_input().split(' '))
  alen = len(bin(a)[2:]) if a > 0 else 0
  vs[-alen-1] += b
  if a <= (K % (2**alen)):
    vs2[-alen] += b

ans = [0]*30
tmp = 0
for i in xrange(-klen, 0):
  ans[i] += vs[i] + tmp
  if kbin[i] == '1':
    tmp += vs2[i]
ans.append(tmp+vs2[0])

print max(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, raw_input().split(' '))
kbin = bin(K)[2:]
klen = len(kbin)

vs = [0]*31
vs2 = [0]*31
for n in xrange(N):
  a, b = map(int, raw_input().split(' '))
  alen = len(bin(a)[2:]) if a > 0 else 0
  vs[-alen-1] += b
  if a <= (K % (2**alen)):
    vs2[-alen] += b

ans = [0]*30
tmp = 0
for i in xrange(-klen, 0):
  ans[i] += vs[i] + tmp
  if kbin[i] == '1':
    tmp += vs2[i]

print max(ans)

Submission status: Wrong Answer

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

kbin = bin(K)[2:]
klen = len(kbin)

vs = [0]*31
vs2 = [0]*31
for n in xrange(N):
  a, b = map(int, raw_input().split(' '))
  abin = bin(a)[2:]
  alen = len(abin)
  vs[-alen-1] += b
  if a <= (K % (2**alen)):
    vs2[-alen] += b

ans = [0]*30
tmp = 0
for i in xrange(-klen, 0):
  ans[i] += vs[i] + tmp
  if kbin[i] == '1':
    tmp += vs2[i]

print max(ans)

Submission status: Wrong Answer

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

kbin = bin(K)[2:]
klen = len(kbin)

vs = [0]*31
vs2 = [0]*31
for n in xrange(N):
  a, b = map(int, raw_input().split(' '))
  abin = bin(a)[2:]
  alen = len(abin)
  vs[-alen-1] += b
  if a <= (K % (2**alen)):
    vs2[-alen] += b

ans = [0]*30
tmp = 0
for i in xrange(-klen, 0):
  ans[i] += vs[i] + tmp
  tmp += vs2[i]

print max(ans)

Submission status: Wrong Answer

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

kbin = bin(K)[2:]
klen = len(kbin)
bits = []
for i in xrange(-klen, 0):
  if kbin[i] == '1':
    bits.append(i)

vs = [0]*30
vs2 = [0]*30
for n in xrange(N):
  a, b = map(int, raw_input().split(' '))
  abin = bin(a)[2:]
  alen = len(abin)
  if a <= (K % (2**alen)):
    vs2[-alen] += b
  for i in xrange(-klen, 0):
    if i < -alen:
      vs[i] += b
    else:
      break

ans = [0]*30
tmp = 0
for i in bits:
  ans[i] += vs[i] + tmp
  tmp += vs2[i]
ans.append(tmp)

print max(ans)

Submission status: Wrong Answer

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

kbin = bin(K)[2:]
klen = len(kbin)
bits = []
for i in xrange(-klen, 0):
  if kbin[i] == '1':
    bits.append(i)

vs = [0]*30
vs2 = [0]*30
for n in xrange(N):
  a, b = map(int, raw_input().split(' '))
  abin = bin(a)[2:]
  alen = len(abin)
  print a, abin, alen, 2**alen
  if a <= (K % (2**alen)):
    vs2[-alen] += b
  for i in xrange(-klen, 0):
    if i < -alen:
      vs[i] += b
    else:
      break

ans = [0]*30
tmp = 0
#print "bits:", bits
#print "vs1:", vs
#print "vs2:", vs2
for i in bits:
  ans[i] += vs[i] + tmp
  tmp += vs2[i]
ans.append(tmp)

#print ans
print max(ans)

Submission status: Wrong Answer

Solution code:
n, k = [int(c) for c in input().split(' ')]
sums = [0] * 30
nums = [[] for _ in range(30)]


def greater_bit_pos(n):
    pos = 0
    while n:
        pos += 1
        n //= 2
    return pos


for i in range(n):
    a, b = [int(c) for c in input().split(' ')]
    pos = greater_bit_pos(a)
    if pos:
        nums[pos - 1].append((a, b))
    for j in range(pos, 30):
        sums[j] += b


def solve(k):
    pos = greater_bit_pos(k)
    if pos == 0:
        ans = sums[0]
    else:
        pos -= 1
        ans = 0
        new_k = k - 2**pos
        for a, b in nums[pos]:
            if a <= k:
                new_a = a - 2**pos
                new_pos = greater_bit_pos(new_k)
                if greater_bit_pos(new_a) < new_pos or new_pos == 0:
                    ans += b
                else:
                    nums[new_pos-1].append((new_a, b))
        ans = max(ans + solve(new_k), sums[pos])
    return ans


print(solve(k))

Submission status: Wrong Answer

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
    if((x | y) ^ y) == 0:
        return True
    else:
        return False


Nstr = list(reversed(bin(K)[2:]))
subNs = [N]
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: Wrong Answer

Solution code:
n, k = [int(c) for c in input().split(' ')]
sums = [0] * 30
nums = [[] for _ in range(30)]


def greater_bit_pos(n):
    pos = 0
    while n:
        pos += 1
        n //= 2
    return pos

for i in range(n):
    a, b = [int(c) for c in input().split(' ')]
    pos = greater_bit_pos(a)
    if pos:
        nums[pos-1].append((a, b))
    for j in range(pos, 30):
        sums[j] += b


def solve(k):
    pos = greater_bit_pos(k)
    if pos == 0:
        ans = sums[0]
    else:
        pos -= 1
        ans = solve(k-2**pos)
        for a, b in nums[pos]:
            if a <= k:
                ans += b
        ans = max(ans, sums[pos])
    return ans

print(solve(k))

Submission status: Wrong Answer

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(a)
    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: Wrong Answer

Solution code:
def main():
    n,k = map(int, input().split())
    base = 0
    scores = [0 for i in range(31)]
    total = 0
    for i in range(n):
        a,b = map(int, input().split())
        if a <= k:
            total += b
            if (a | k) <= k:
                base += b
            v = 1
            idx = 0
            while v <= a: 
                if v & a > 0:
                    scores[idx] += b
                idx += 1
                v *= 2
    mask = []
    v = 1
    idx = 0
    while v <= k:
        if v & k == 0:
            mask.append(False)
        else:
            mask.append(True)
        idx += 1
        v *= 2
    gain = [0]
    for i, mask_i in enumerate(mask):
        gain.append(gain[-1] + (0 if mask_i else scores[i]))
    # gain = gain[1:]

    # print(scores)
    # print(total)
    # print(mask)
    # print(gain)
    # print("base", base)
    max_v = base
    for i, mask_i in enumerate(mask):
        if mask_i:
            max_v = max(max_v, base - scores[i] + gain[i])
    print(max_v)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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]
# print(A)
L = K.bit_length()
ans = 0
for i in reversed(range(L)):
    bit = (1 << i) & K
    if bit != 1:
        # print(bit, ':', i)
        cand = 0
        for a, b in A:
            if ((a >> i) & 1) == 0:
                # print(a, (a >> i) & 1)
                cand += b
        ans = max(ans, cand)
print(ans)

Submission status: Wrong Answer

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

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

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]
        m=bin(a)
        if int(i,0)>=a:
            for l in range(min(len(m),len(i))):
                if i[-1-l]=="0" and m[-1-l]=="1":
                    break
            else:
                tmp+=b
    ans=max(ans,tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, k = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(n)]
    ans = 0
    for a, b in arr:
        f = True
        for i in range(32):
            if k & (1<<i) == 0 and a & (1<<i) != 0:
                f = False
                break
        if f:
            ans += b
    for i in range(32):
        p = 1<<i
        tmp = 0
        if p & k == 0:
            continue
        for a, b in arr:
            if a <= k and a&p == 0:
                f = True
                for j in range(i+1, 32):
                    if k & (1<<j) == 0 and a & (1<<j) != 0:
                        f = False
                        break
                if f:
                    tmp += b
        if ans < tmp:
            ans = tmp
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

n,k = map(int,input().split())
A = [set(range(30)) for _ in range(n)]
B = [0]*n
for i in range(n):
    a,b = map(int,input().split())
    j = 0
    while a > 0:
        if a&1:A[i].remove(j)
        j += 1
        a = a >> 1
    B[i] = b
bit = [0]*30
j = 0
while k > 0:
    bit[j] = k&1
    k = k >> 1
    j += 1
zero = set()
ans = 0
def check(Z):
    res = 0
    for j in range(n):
        for z in Z:
            if z not in A[j]:break
        else:
            res += B[j]
    return res

for i in range(29,-1,-1):
    b = bit[i]
    if b == 0:
        zero.add(i)
    else:
        zero.add(i)
        ans = max(ans,check(zero))
        zero.remove(i)
ans = max(ans,check(zero))
print(ans)

Submission status: Time Limit Exceeded

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):
    test=0
    for j in range(N):
        a,b=integer[j]
        if a|K==K:
            test+=b
    ans=max(ans,test)

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

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

# 各商品の価格のビットが立っている位置を事前に見とく
bit = []
for a, b in AB:
    tmp = set()
    for i in range(31):
        if a & 1:
            tmp.add(i)
        a //= 2
    bit.append((tmp, b))

def cost(S):
    res = 0
    for T, b in bit:
        if S.issuperset(T):
            res += b
    return res

# Kのビットが立っている位置を調べる
Kbit = set()
Ktmp = K
for i in range(31):
    if Ktmp & 1:
        Kbit.add(i)
    Ktmp //= 2

ans = cost(Kbit)
for i in Kbit:
    T = Kbit.copy()
    T -= {i}            #位置iのビットを0にする
    T |= set(range(i))  #i未満のビットを全部1にする
    ans = max(ans, cost(T))

print(ans)

Submission status: Time Limit Exceeded

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

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 = format(AB[j][0],'b')

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

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:
    f=0
    for i in range(30):
        if a//(2**(29-i))==1 and k[i]==0:
            f=1
            break
        else:
            a%=(2**(29-i))
    if f==0:
        ans+=b
NUM=0

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

Submission status: Time Limit Exceeded

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

visited = defaultdict(lambda : False)
L = set()
def dfs(x) :
    if visited[x] :
        return 
        
    visited[x] = True
    for i in range(30) :
        if x & (1 << i) == 0 :
            continue
            
        y = x ^ (1 << i)
        if y <= K :
            L.add(y)
        else :
            dfs(y)


dfs((1 << (len(bin(K)) - 2)) - 1)
L.add(K)

ret = 0
for mask in L :
    s = 0
    for A, B in AB :
        if A & ~mask == 0 :
            s += B
    ret = max(ret, s)
    
print(ret)

Submission status: Time Limit Exceeded

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

def dfs(x, fr) :
    flag = True
    M = 0
    for i in range(fr, 30) :
        y = x | (1 << i)
        if y <= K :
            M = max(M, dfs(y, i + 1))
            flag = False
            
    if flag :
        s = 0
        for A, B in AB :
            if A & ~x == 0 :
                s += B
        return s
    else :
        return M
        
print(dfs(0, 0))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = [[0 for _ in range(N)] for _ in range(30)]
B = [0] * N
for i in range(N):
  a, b = map(int, input().split())
  for j in range(30):
    A[j][i] = a % 2
    a //= 2
  B[i] = b
M = [0] * 30
_M = [0] * N
_K = K
for i in range(30):
  k = _K % 2
  M[i] = k
  _K //= 2
  if k:
    continue
  for j in range(N):
    _M[j] += A[i][j]
cnt = 0
for i in range(N):
  if _M[i]:
    continue
  cnt += B[i]
Z = [0] * N
for i in range(30):
  if M[i] == 0:
    for j in range(N):
      Z[j] += A[i][j]
  else:
    _cnt = 0
    for j in range(N):
      _M[j] += A[i][j] - Z[j]
      Z[j] = A[i][j]
      if _M[j]:
        continue
      _cnt += B[j]
    cnt = max(_cnt, cnt)
print(cnt)

Submission status: Time Limit Exceeded

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
        if ok:
            ans_k += B
    ans = max(ans, ans_k)

print(ans)

Submission status: Time Limit Exceeded

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

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

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

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 i in range(N):
        A = int_list[i]
        if int(k, 2) - int(A, 2) == int(k, 2) ^ int(A, 2):
            ans_k += val_list[i]
    ans = max(ans, ans_k)

print(ans)

Submission status: Time Limit Exceeded

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

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

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

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 i in range(N):
        A = int_list[i]
        if len(A) > max_len:
            continue
        ok = 1
        for j, a in enumerate(A):
            if a == '1' and k[j] == '0':
                ok = 0
        if ok:
            ans_k += val_list[i]
    ans = max(ans, ans_k)

print(ans)

Submission status: Time Limit Exceeded

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

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

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 i in range(N):
        A = int_list[i]
        if len(A) > max_len:
            continue
        ok = 1
        for j, a in enumerate(A):
            if a == '1' and k[j] == '0':
                ok = 0
        if ok:
            ans_k += val_list[i]
    ans = max(ans, ans_k)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
import copy
import sys
input=sys.stdin.readline
D=dict()
D[(0,0)]=1

for i in range(N):
    a,b=map(int,input().split())
    d=dict()
    for j in D:
        d[j]=1
        d[(j[0]|a,j[1]+b)]=1
    D=copy.deepcopy(d)
#print(D)
ans=0
for i in D:
    if i[1]>ans and i[0]<=K:
        ans=i[1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def issubset(a,b):
    #a<<bならtrue
    x=bin(a)[2:]
    y=bin(b)[2:]
    if a>b:
        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())
Kl=[K]
Ks=bin(K)[2:]
for i,c in enumerate(Ks):
    if c=="1":
        Kl.append(int(Ks[:i]+"0"+"1"*(len(Ks)-i-1),2))
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)