Подарунок для Леді

Козак Вус довго думав, що подарувати Леді на День Народження. Він вирішив зробити оригінальний і, найголовніше, корисний подарунок. Тому Козак Вус подарував Леді набір пар з чисел $(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$, якщо не розглядати старші біти, які рівні $0$. Тоді операція АБО застосовується до кожного біту. Таким чином нульовий біт рівний $(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$ бали): без додаткових обмежень.