Russel Supremacy

★★★★★

2 votes

Bit manipulation, Medium

Details

Problem

After Performing well in IPL, everyone's expectation has increased from Russel.This time Russel needs to solve a programming question.Given $n$ (key,value) pairs and a number $K$ . You have to pick some keys such that

Bitwise OR of chosen keys is $\leq K$ .
Sum of corresponding values is maximum.

Print the maximum sum of values that can be achieved.

But Russel doesn't know programmiing ,so you being Russel's die hard supporter needs to help him solve this question to prove his supremacy here as well.

Input Format:

First Line will consist of n and K denoting the number of key value pairs and K as specisied in the problem statement.

Next n lines contain key,value pairs.

Output Format:

Output the required answer in the single line.

Constraints:

$1 \leq N \leq 10^5 \\ 0 \leq K \leq 1073741823 \\ 0 \leq key_i \leq 1073741823 \\ 1 \leq value_i \leq 10^9(1≤i≤N)$

Sample Input

Sample Output

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

You can choose 1^st and 3^rd key which maximizes the sum of corresponding values (3+5=8). It can be proven that sum greater than 8 cannot be achieved.