/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 500 点
問題文
非負整数専門店「せいすうや」には、N 個の非負整数が売られています。i 個目の非負整数は A_i で、その価値は B_i です。 価値の異なる同じ非負整数が複数売られていることもあります。
高橋君は、「せいすうや」でいくつかの整数を買うことにしました。高橋君は、買う整数たちの bitwise or が K 以下になるような 任意の組み合わせで、整数を買うことができます。高橋君は、買った整数たちの価値の総和をできるだけ大きくしたいです。
高橋君が達成できる、価値の総和の最大値を求めてください。ただし、bitwise or とは、ビットごとの論理和を表します。
制約
- 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)
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 B_1 : A_N B_N
出力
高橋君が達成できる価値の総和の最大値を出力せよ。
入力例 1
3 5 3 3 4 4 2 5
出力例 1
8
2 と 3 を購入することで、最大値 8 を達成できます。
入力例 2
3 6 3 3 4 4 2 5
出力例 2
9
2 と 4 を購入することで、最大値 9 を達成できます。
入力例 3
7 14 10 5 7 4 11 4 9 8 3 6 6 2 8 9
出力例 3
32
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