A Gift for the Lady#10359

A Gift for the Lady

2 seconds

256 megabytes

Hard

Kozak Vus spent a long time deciding on the perfect birthday gift for Lady. He wanted it to be both unique and practical, so he gave her a collection of number pairs $(a_{i}, b_{i})$ (a_i, b_i), with a total of $n$ pairs.

Initially, Lady was puzzled by this unusual gift. The original set didn't quite appeal to her, so she decided to select a subset of these pairs that would meet specific criteria.

Lady aims to form a new set, which is a subset of the original one. Formally, this subset consists of pairs $(a_{i_{1}}, b_{i_{1}}), (a_{i_{2}}, b_{i_{2}}), \dots, (a_{i_{m}}, b_{i_{m}})$ (a_{i_1}, b_{i_1}), (a_{i_2}, b_{i_2}), \dots, (a_{i_m}, b_{i_m}), where $0 \leq m \leq n$ 0 \leq m \leq n and for all $1 \leq p \leq m - 1$ 1 \leq p \leq m-1, it holds that $i_{p} < i_{p + 1}$ i_p < i_{p+1}. Lady can choose anywhere from $0$ to all $n$ pairs.

Lady considers a set to be the most beautiful if it satisfies the following conditions:

Lady's favorite number is $k$ . Therefore, the bitwise OR of all selected $a_{i_{p}}$ a_{i_p} for $1 \leq p \leq m$ 1 \leq p \leq m must not exceed $k$ .
The sum of all $b_{i_{p}}$ b_{i_p} for $1 \leq p \leq m$ 1 \leq p \leq m should be maximized.

The bitwise OR operation (denoted as $∣$ ) is performed on each bit of the numbers, resulting in $0$ if both bits are $0$ , and $1$ otherwise. For example, consider the numbers $9$ and $10$ . Their binary forms are $1001$ and $1010$ . Applying the OR operation bit by bit, the result is $1011$ , which equals $11$ in decimal.

Lady is struggling to find the most beautiful set. She realizes this is a challenging task, so she only asks you to determine the maximum possible sum of all $b_{i_{p}}$ b_{i_p} in the most beautiful set.

Input

The first line contains two integers $n$ and $k$ ( $1 \leq n \leq 1 0^{6}$ 1 \leq n \leq 10^6, $0 \leq k < 2^{30}$ 0 \leq k < 2^{30}).

Each of the next $n$ lines contains two integers $a_{i}$ a_i and $b_{i}$ b_i ( $0 \leq a_{i}, b_{i} < 2^{30}$ 0 \leq a_i, b_i < 2^{30}).

Output

Output a single number — the maximum possible sum of the selected $b_{i_{p}}$ b_{i_p}.

Examples

Example 1

Example 2

Note

In the first example, selecting the first and second pairs results in a bitwise OR of $7$ , with a sum of $2$ . It's impossible to increase the sum because including all three pairs results in a bitwise OR of $15$ , which exceeds $k$ .

In the second example, the optimal choice is the second, third, and fourth pairs, yielding a sum of $6$ . Including the first pair would limit the selection to only the third pair to keep the bitwise OR within $k$ . Thus, the maximum possible sum is $6$ .

Scoring

( $17$ points): $n \leq 10$ n \leq 10;
( $26$ points): $n \leq 1 0^{4}$ n \leq 10^4, $k < 2^{10}$ k < 2^{10};
( $14$ points): $k = 2^{t} - 1$ k = 2^t -1, where $0 \leq t \leq 30$ 0 \leq t \leq 30;
( $43$ points): no additional restrictions.