A Gift for the Lady

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)$, 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})$, where $0\le m\le n$ and for all $1\le p\le m-1$, it holds that $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:

1. Lady's favorite number is $k$. Therefore, the bitwise OR of all selected $a_{i_p}$ for $1\le p\le m$ must not exceed $k$. 2. The sum of all $b_{i_p}$ for $1\le p\le 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}$ in the most beautiful set.

Input

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

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

Output

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

Examples

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

1. ($17$ points): $n\le 10$;

2. ($26$ points): $n\le 10^4$, $k<2^{10}$;

3. ($14$ points): $k=2^t-1$, where $0\le t\le 30$;

4. ($43$ points): no additional restrictions.