Подарок для Леди

Козак Вус долго размышлял над тем, что подарить Леди на День Рождения. В итоге он решил сделать оригинальный и, что самое важное, полезный подарок. Поэтому он подарил ей набор пар чисел $(a_i,b_i)$ длиной $n$.

Сначала Леди не поняла, зачем ей такой странный набор чисел. Поскольку начальный набор ей не очень понравился, она решила выбрать подмножество пар из этого набора, которые будут удовлетворять определённым условиям.

Пусть Леди выбрала новый набор, который является подмножеством начального. Формально, подмножество — это набор пар $(a_{i_1},b_{i_1}),(a_{i_2},b_{i_2})\dots (a_{i_m},b_{i_m})$, где $0\le m\le n$ и для всех $1\le p\le m-1$ выполняется $i_p<i_{p+1}$. Заметим, что Леди может выбрать как $0$ пар, так и все $n$ пар.

Леди считает, что полученный набор самый красивый из всех возможных, если выполняются два условия:

1. Всем известно, что любимое число Леди — $k$. Поэтому побитовое ИЛИ всех выбранных $a_{i_p}$ для $1\le p\le m$ не должно превышать число $k$. 2. Сумма всех $b_{i_p}$ для $1\le p\le m$ должна быть максимальной.

Побитовое ИЛИ (обозначается $|$) — это операция, которая выполняется для каждого из битов, и результат равен $0$ только тогда, когда оба бита чисел равны $0$. В противном случае бит равен $1$. Например, для чисел $9$ и $10$ их двоичные записи — $1001$ и $1010$. Операция ИЛИ применяется к каждому биту: нулевой бит равен $(1|0)=1$, первый бит — $(0|1)=1$, второй бит — $(0|0)=0$, третий бит — $(1|1)=1$. Таким образом, побитовое ИЛИ чисел $9$ и $10$ в двоичной записи — $1011$, что равно $11$.

Леди столкнулась с проблемой поиска самого красивого набора. Она понимает, что это сложная задача, поэтому просит вас только сообщить сумму всех $b_{i_p}$ в самом красивом наборе.

Входные данные

Первая строка содержит два целых числа $n$ и $k$ ($1\le n\le 10^6$, $0\le k<2^{30}$).

Каждая из следующих $n$ строк содержит по два целых числа $a_i$ и $b_i$ ($0\le a_i,b_i<2^{30}$).

Выходные данные

Выведите одно число — максимально возможную сумму выбранных $b_{i_p}$.

Примеры

Примечание

В первом примере, если выбрать первую и вторую пару, то побитовое ИЛИ будет равно $7$, а сумма — $2$. Увеличить сумму невозможно, так как если взять все три пары, побитовое ИЛИ будет равно $15$, что превышает $k$.

Во втором примере выгоднее всего выбрать вторую, третью и четвёртую пары, чтобы получить ответ $6$. Если выбрать первую пару, то с ней можно взять только третью пару, чтобы побитовое ИЛИ не превышало $k$. Таким образом, максимально возможная сумма равна $6$.

Оценивание

1. ($17$ баллов): $n\le 10$; 2. ($26$ баллов): $n\le 10^4$, $k<2^{10}$; 3. ($14$ баллов): $k=2^t-1$, где $0\le t\le 30$; 4. ($43$ балла): без дополнительных ограничений.