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:
# -*- coding: utf-8 -*-
import sys,copy,math,heapq,itertools as it,fractions,re,bisect,collections as coll

N, K = map(int, raw_input().split())
AB = [map(int, raw_input().split()) for i in xrange(N)]

b = bin(K)
bs = [K]
for i in xrange(len(b) - 1):
    nb = list(b)
    nb[i] = "0"
    nb[i + 1:] = ["1"]*len(nb[i + 1:])
    nb = int("".join(nb), 2)
    if nb <= K:
        bs.append(nb)

ans = 0
for v in bs:
    cur = 0
    for A, B in AB:
        if v|A <= v:
            cur += B
    ans = max(ans, cur)
print ans

Submission status: Accepted

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

def solve(P):
    res = 0
    for a, b in V:
        if P & a == a:
            res += b
    return res
ans = solve(K)
for i in range(32):
    if K & (1 << i):
        P = (K | ((1 << i)-1) )^ (1 << i)
        ans = max(ans, solve(P))
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, raw_input().split())
aa = []
bb = []
for i in range(n):
    a,b = map(int, raw_input().split())
    aa.append(a)
    bb.append(b)

ans = 0

def hoge(x, k):
    xx = x
    if (x & (1 << k)) == 0:
        return x
    for i in range(k):
        x |= (1<<i)
    x -= 1 << k
    return min(xx,x)
        

for j in range(31):
    kk = hoge(k, j)
    res = 0
    for i in range(n):
        if (aa[i]|kk) == kk:
            res += bb[i]
    ans = max(ans, res)

print(ans)

Submission status: Runtime Error

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
    ans = max(vals.values())
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
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: Runtime Error

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

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

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

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

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

print(max(ANS))

Submission status: Runtime Error

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

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

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

A = [[] for _ in range(k+1)]
B = [0]*(k+1)
for i in range(N):
    a,b = AB[i]
    for j in range(k):
        if a[j] == K[j] == 1:
            B[j+1] -= b
        if a[j] > K[j]:
            A[j].append(b)
            break
    else:
        A[k].append(b)


for i in range(k+1):
    A[i] = sum(A[i])

for i in range(k-1,-1,-1):
    A[i] += A[i+1]

print(max(A[i]+B[i] for i in range(1,k+1)))

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

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

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

A = [[] for _ in range(k+1)]
B = [0]*(k+1)
for i in range(N):
    a,b = AB[i]
    for j in range(k):
        if a[j] == 1:
            B[j+1] -= b
        if a[j] > K[j]:
            A[j].append(b)
            break
    else:
        A[k].append(b)


for i in range(k+1):
    A[i] = sum(A[i])

for i in range(k-1,-1,-1):
    A[i] += A[i+1]

c = 0
for i in range(N):
    a,b = AB[i]
    if a[0] == 0:
        c += b

print(max(c,max(A[i]+B[i] for i in range(1,k+1))))

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

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

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

A = [[] for _ in range(k+1)]
B = [0]*(k+1)
for i in range(N):
    a,b = AB[i]
    for j in range(k):
        if a[j] == 1:
            B[j+1] -= b
        if a[j] > K[j]:
            A[j].append(b)
            break
    else:
        A[k].append(b)


for i in range(k+1):
    A[i] = sum(A[i])

for i in range(k-1,-1,-1):
    A[i] += A[i+1]

print(max(A[i]+B[i] for i in range(1,k+1)))

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

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

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

A = [[] for _ in range(k+1)]
B = [0]*(k+1)
for i in range(N):
    a,b = AB[i]
    for j in range(k):
        if a[j] == 1 and j >= 1:
            B[j] -= b
        if a[j] > K[j]:
            A[j].append(b)
            break
    else:
        A[k].append(b)


for i in range(k+1):
    A[i] = sum(A[i])

for i in range(k-1,-1,-1):
    A[i] += A[i+1]

print(max(A[i]+B[i] for i in range(1,k+1)))

Submission status: Runtime Error

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: Runtime Error

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: Runtime Error

Solution code:
print(1)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using ull=unsigned long long;
using uint=unsigned int;
using pcc=pair<char,char>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using pdd=pair<double,double>;
using tuplis=pair<ll,pll>;
using tuplis2=pair<pll,ll>;
template<class T> using pq=priority_queue<T,vector<T>,greater<T>>;
const ll LINF=0x1fffffffffffffff;
const int INF=0x3fffffff;
const ll MOD=1000000007;
const ll MODD=998244353;
const ld DINF=numeric_limits<ld>::infinity();
const ld EPS=1e-9;
const vector<ll>four{0,1,0,-1,0};
#define _overload4(_1,_2,_3,_4,name,...) name
#define _overload3(_1,_2,_3,name,...) name
#define _rep1(n) for(ll i=0;i<n;++i)
#define _rep2(i,n) for(ll i=0;i<n;++i)
#define _rep3(i,a,b) for(ll i=a;i<b;++i)
#define _rep4(i,a,b,c) for(ll i=a;i<b;i+=c)
#define rep(...) _overload4(__VA_ARGS__,_rep4,_rep3,_rep2,_rep1)(__VA_ARGS__)
#define _rrep1(n) for(ll i=n-1;i>=0;i--)
#define _rrep2(i,n) for(ll i=n-1;i>=0;i--)
#define _rrep3(i,a,b) for(ll i=b-1;i>=a;i--)
#define _rrep4(i,a,b,c) for(ll i=a+(b-a-1)/c*c;i>=a;i-=c)
#define rrep(...) _overload4(__VA_ARGS__,_rrep4,_rrep3,_rrep2,_rrep1)(__VA_ARGS__)
#define each(i,a) for(auto &i:a)
#define sum(...) accumulate(range(__VA_ARGS__),0LL)
#define dsum(...) accumulate(range(__VA_ARGS__),double(0))
#define _range(i) (i).begin(),(i).end()
#define _range2(i,k) (i).begin(),(i).begin()+k
#define _range3(i,a,b) (i).begin()+a,(i).begin()+b
#define range(...) _overload3(__VA_ARGS__,_range3,_range2,_range)(__VA_ARGS__)
#define _rrange(i) (i).rbegin(),(i).rend()
#define _rrange2(i,k) (i).rbegin(),(i).rbegin()+k
#define _rrange3(i,a,b) (i).rbegin()+a,(i).rbegin()+b
#define rrange(...) _overload3(__VA_ARGS__,_rrange3,_rrange2,_rrange)(__VA_ARGS__)
#define elif else if
#define unless(a) if(!(a))
#define mp make_pair
#define mt make_tuple
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define ULL(...) ull __VA_ARGS__;in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;in(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;in(__VA_ARGS__)
#define vec(type,name,...) vector<type> name(__VA_ARGS__)
#define VEC(type,name,size) vector<type> name(size);in(name)
#define vv(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__))
#define VV(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__));in(name)
#define vvv(type,name,h,w,...) vector<vector<vector<type>>>name(h,vector<vector<type>>(w,vector<type>(__VA_ARGS__)))
inline constexpr ll gcd(ll a,ll b){if(!a||!b)return 0;while(b){ll c=b;b=a%b;a=c;}return a;}
inline constexpr ll lcm(ll a,ll b){if(!a||!b)return 0;return a*b/gcd(a,b);}
template<class T> inline constexpr T min(vector<T> &v){return *min_element(range(v));}
inline char min(string &v){return *min_element(range(v));}
template<class T> inline constexpr T max(vector<T> &v){return *max_element(range(v));}
inline char max(string &v){return *max_element(range(v));}
inline constexpr ll intpow(ll a,ll b){ll ans=1;for(ll i=1;b;i*=2){if(b&i){b^=i;ans*=a;}a*=a;}return ans;}
inline constexpr ll modpow(ll a,ll b,ll mod = MOD){ll ans=1;for(ll i=1;b;i*=2){if(b&i){b^=i;ans*=a;ans%=mod;}a*=a;a%=mod;}return ans;}
template<typename T>
inline constexpr bool update_min(T &mn,const T &cnt){if(mn>cnt){mn=cnt;return 1;}else return 0;}
template<typename T>
inline constexpr bool update_max(T &mx,const T &cnt){if(mx<cnt){mx=cnt;return 1;}else return 0;}
inline int scan(){ return getchar(); }
inline void scan(int &a){ scanf("%d", &a); }
inline void scan(unsigned &a){ scanf("%u", &a); }
inline void scan(long &a){ scanf("%ld", &a); }
inline void scan(long long &a){ scanf("%lld", &a); }
inline void scan(unsigned long long &a){ scanf("%llu", &a); }
inline void scan(char &a){ cin >> a; }
inline void scan(float &a){ scanf("%f", &a); }
inline void scan(double &a){ scanf("%lf", &a); }
inline void scan(long double &a){ scanf("%Lf", &a); }
inline void scan(vector<bool> &vec){ for(unsigned i = 0; i < vec.size(); i++) { int a; scan(a); vec[i] = a; } }
inline void scan(string &a){ cin >> a; }
template<class T> inline void scan(vector<T> &vec);
template<class T, size_t size> inline void scan(array<T, size> &vec);
template<class T, class L> inline void scan(pair<T, L> &p);
template<class T, size_t size> inline void scan(T (&vec)[size]);
template<class T> inline void scan(vector<T> &vec){ for(auto &i : vec) scan(i); }
template<class T, size_t size> inline void scan(array<T, size> &vec){ for(auto &i : vec) scan(i); }
template<class T, class L> inline void scan(pair<T, L> &p){ scan(p.first); scan(p.second); }
template<class T, size_t size> inline void scan(T (&vec)[size]){ for(auto &i : vec) scan(i); }
template<class T> inline void scan(T &a){ cin>>a; }
inline void in(){}
template <class Head, class... Tail> inline void in(Head &head, Tail&... tail){ scan(head); in(tail...); }
inline void print(){ putchar('\n'); }
inline void print(const bool &a){ printf("%d", a); }
inline void print(const int &a){ printf("%d", a); }
inline void print(const unsigned &a){ printf("%u", a); }
inline void print(const long &a){ printf("%ld", a); }
inline void print(const long long &a){ printf("%lld", a); }
inline void print(const unsigned long long &a){ printf("%llu", a); }
inline void print(const char &a){ printf("%c", a); }
inline void print(const char a[]){ printf("%s", a); }
inline void print(const float &a){ printf("%.10f", a); }
inline void print(const double &a){ printf("%.10f", a); }
inline void print(const long double &a){ printf("%.10Lf", a); }
template<class T> void print(const vector<T> &vec);
template<class T, size_t size> void print(const array<T, size> &vec);
template<class T, class L> void print(const pair<T, L> &p);
template<class T, size_t size> inline void print(const T (&vec)[size]);
template<class T> void print(const vector<T> &vec){ print(vec[0]); for(auto i = vec.begin(); ++i != vec.end(); ){ putchar(' '); print(*i); } }
template<class T, size_t size> void print(const array<T, size> &vec){ print(vec[0]); for(auto i = vec.begin(); ++i != vec.end(); ){ putchar(' '); print(*i); } }
template<class T, class L> void print(const pair<T, L> &p){ print(p.first); putchar(' '); print(p.second); }
template<class T, size_t size> inline void print(const T (&vec)[size]){ print(vec[0]); for(auto i = vec; ++i != end(vec); ){ putchar(' '); print(*i); } }
template<class T> inline void print(const T &a){ cout << a; }
inline int out(){ putchar('\n'); return 0; }
template<class T> inline int out(const T &t){ print(t); putchar('\n'); return 0; }
template<class Head, class... Tail> inline int out(const Head &head, const Tail&... tail){ print(head); putchar(' '); out(tail...); return 0; }
template <class T> inline void err(T t){cerr<<t<<'\n';}
inline void err(){cerr<<'\n';}
inline int yes(const bool &i){return out(i?"yes":"no");}
inline int Yes(const bool &i){return out(i?"Yes":"No");}
inline int YES(const bool &i){return out(i?"YES":"NO");}
inline int Yay(const bool &i){return out(i?"Yay!":":(");}
inline int Possible(const bool &i){return out(i?"Possible":"Impossible");}
inline int POSSIBLE(const bool &i){return out(i?"POSSIBLE":"IMPOSSIBLE");}
inline void Case(ll i){printf("Case #%lld: ",i);}






int main(){
    long n, k;
    cin >> n >> k;
    vector<long> a(n), b(n);
    for(long i = 0; i < n; i++){
        cin >> a[i] >> b[i];
    }
    auto point = [&](long k){
        long ans = 0;
        for(long i = 0; i < n; i++){
            if((a[i] | k) == k) ans += b[i];
        }
        return ans;
    };
    long ans = point(k);
    for(long i = 0; i < 30; i++) if((k >> i) & 1){
        long K = k;
        K ^= 1 << i;
        K |= (1 << i) - 1;
        long tmp = point(K);
        if(ans < tmp) ans = tmp;
    }
    cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
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: Runtime Error

Solution code:
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: Runtime Error

Solution code:
#エラーはここか否か
n,k=map(int, input().split( ))
s = [tuple(map(int, input().split( ))) for _ in range(n)]

kk=[k]+[((((k>>i)-1)<<i) + (1<<i) -1)  for i in range(1,k.bit_length()) if (k>>i)&1]

Submission status: Runtime Error

Solution code:
#解説参照
#xor ではなく or

n,k=map(int, input().split( ))
s = [tuple(map(int, input().split( ))) for _ in range(n)]

kk=[k]+[((((k>>i)-1)<<i) + (1<<i) -1)  for i in range(1,k.bit_length()) if (k>>i)&1]
#print(kk)
ans=0
for ki in kk:
    tmp = 0
    for ai,bi in s:
        flag=True##ここ
        for j in range(k.bit_length()):
            if ((ai>>j)&1) > ((ki>>j)&1):
                flag=False
                break
        if flag:
            tmp+=bi
    ans=max(ans,tmp)
print(ans)

Submission status: Runtime Error

Solution code:
#解説参照
#xor ではなく or

n,k=map(int, input().split( ))
s = [tuple(map(int, input().split( ))) for _ in range(n)]

kk=[k]+[((((k>>i)-1)<<i) + (1<<i) -1)  for i in range(1,k.bit_length()) if (k>>i)&1]
#print(kk)
ans=0
for ki in kk:
    tmp = 0
    tmp2=[]
    for ai,bi in s:
        flag=True##ここ
        for j in range(k.bit_length()):
            if ((ai>>j)&1) > ((ki>>j)&1):
                flag=False
                break
        if flag:
            tmp+=bi
            tmp2.append((ai,bi))
    ans=max(ans,tmp)
print(ans)

Submission status: Runtime Error

Solution code:
INF = 10 ** 15
MOD = 10 ** 9 + 7 
from collections import deque

def main():
    N,K = map(int,input().split())
    number = [tuple(map(int,input().split())) for _ in range(N)]

    msb = 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: Runtime Error

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 = []
l = k.bit_length()
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: Runtime Error

Solution code:
n,k = map(int,input().split())
a = [list(map(int,input().split())) for i in range(n)]
ans = []
l = k.bit_length()
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: Runtime Error

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:
                ans += b
        return res
    ans = f(k)
    for i in range(31):
        if k & (1 << i):
            K = (k | ((1 << i) - 1)) ^ (1 << i)
            res = f(K)
            if ans < res:
                ans = res
    print(ans)
    return


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

Submission status: Runtime Error

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():
    def dfs(j):
        lj = l[j]
        if j == len(l)-1:
            return s[1<<lj]+f[lj]
        nj = j+1
        lnj = l[nj]
        p = (1<<lj)|((1<<lnj)-1)
        res_ = 0
        for a,b in v:
            if a&p == a:
                res_ += b
        res = s[1<<lj]+max(dfs(nj),f[lnj])
        return max(res,res_,f[lj])
    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]
    print(dfs(0))
    return


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

Submission status: Runtime Error

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

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

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

ma = 0
ma = max(ma, chk( (1<<(keta-1))-1) )
ma = max(ma, chk ( K ) )

for i in range(keta):
  if ( kbit[keta-1-i] == 0 ):
    continue
  else:
    bit = [0]*(keta)
    for j in range(keta):
      if (i<j):
        bit[keta-1-j]=1
      elif (j<i):
        bit[keta-1-j]=kbit[keta-1-j]
      else:
        bit[keta-1-j]=0
    
    v = 0
    for j in range(keta):
      if (bit[j]==1):
        v += 2**(j)
    #print ( v , bit )
    ma = max(ma, chk ( v ) )
print ( ma )

Submission status: Runtime Error

Solution code:
N, K = [int(i) for i in input().split()]
pairs = []
kouhos= []
zero_index = []
one_index = []

for i in range(N):
    A, B = [int(j) for j in input().split()]
    pairs.append((A,B))

binK = bin(K)[2:]
lenK = len(binK)

for i in range(lenK):
    if binK[i]=='0':
        zero_index.append(i)
    else:
        one_index.append(i)

sums = 0
for (x,v) in pairs:
    binx = bin(x)[2:]
    #lenx = len(binx)
    if x<=K:
        for index in zero_index:
            if binx[-(lenK-index)]!='0':
                break
        else:
            sums += v

kouhos.append(sums)

for index in one_index:
    seq = binK[:index]+'0'
    #seq = seq
    bound = int(seq, 2) <<(lenK-index-1)
    up  = bound + 2**(lenK-index-1)

    sums=0
    for (a,b) in pairs:
        if bound<=a and a<up:
            sums += b

    kouhos.append(sums)


print(max(kouhos))

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
import copy
import heapq
import math

from math import *

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

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

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

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

    print max_value



if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math

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

        tmp_sum = 0

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

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

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

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

Submission status: Runtime Error

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

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

print(answer)

Submission status: Runtime Error

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

ans = 0

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

print(ans)

Submission status: Runtime Error

Solution code:
N, K = map(int, raw_input().split(' '))
klen = len(bin(K)[2:]) 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: Runtime Error

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