e-olymp
Yarışlar

Ukrainian Olympiad in Informatics, III Stage, I Round

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

Козак Вус довго думав, що подарувати Леді на День Народження. Він вирішив зробити оригінальний і, найголовніше, корисний подарунок. Тому Козак Вус подарував Леді набір пар з чисел $(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 \leq m \leq n$ і для усіх $1 \leq p \leq m-1$ виконується $i_p < i_{p+1}$. Зауважимо, що Леді може вибрати як $0$ пар, так й усі $n$ пар. Леді вважає, що отриманий набір найгарніший з усіх можливих наборів, якщо виконуються дві умови: \begin{enumerate} \item Усім відомо, що улюблене число Леді --- $k$. Тому побітове АБО усіх вибраних $a_{i_p}$ для $1 \leq p \leq m$ має не перевищувати число $k$. \item Сума усіх $b_{i_p}$ для $1 \leq p \leq m$ --- максимальна. \end{enumerate} Побітове АБО (позначаємо $|$)--- операція, що виконується до кожного з бітів, в результаті отримується $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}$ у найгарнішому наборі. \InputFile Перший рядок містить два цілі числа $n$ та $k$ ($1 \leq n \leq 10^6$, $0 \leq k < 2^{30}$). Кожен з наступних $n$ рядків містить по два цілі числа $a_i$ та $b_i$ ($0 \leq a_i, b_i < 2^{30}$). \OutputFile Виведіть одне число --- максимально можливу суму вибраних $b_{i_p}$. \Note У першому прикладі, якщо взяти першу та другу пару у відповідь, то отримаємо побітове АБО рівне $7$, а шукану суму рівну 2. Збільшити суму неможливо, бо якщо взяти усі три пари отримаємо побітове АБО рівне $15$, що перевищує $k$. У другому прикладі найвигідніше буде взяти другу, третю та четверту пари, щоб отримати відповідь $6$. Якщо взяти до відповіді першу пару, то з нею в набір можна взяти лише третю пару, щоб отримати побітове АБО не більше за $k$. Таким чином максимально можлива сума рівна $6$. \Scoring \begin{enumerate} \item ($17$ балів): $n \leq 10$; \item ($26$ балів): $n \leq 10^4$, $k < 2^{10}$; \item ($14$ балів): $k = 2^t -1$, де $0 \leq t \leq 30$; \item ($43$ бали): без додаткових обмежень. \end{enumerate}
Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB
Giriş verilənləri #1
3 10
5 1
3 1
10 1
Çıxış verilənləri #1
2
Giriş verilənləri #2
4 12
8 3
6 2
1 2
5 2
Çıxış verilənləri #2
6
Müəllif Sofia Melnyk