题目描述

哥萨克胡子想了很久，在女士生日那天送她什么礼物。他决定送一件既独特又最重要的——是有用的礼物。于是，哥萨克胡子送给女士一套由 $n$ 对数字 $(a_i, b_i)$ 组成的礼物。

女士起初不明白，为什么给她这样一套奇怪的数字。最初的这套礼物她不太喜欢，因此她决定从这个礼物集合中选择一个子集，这个子集需要满足特定的条件。

假设女士得到了一个新集合，它是原始集合的一个子集。形式化地说，子集是若干对数字构成的集合：$(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$ 对。

女士认为，如果满足以下两个条件，那么得到的集合是所有可能集合中最 优美 的：

• 众所周知，女士最喜欢的数字是 $k$。因此，所有选中的 $a_{i_p}$（$1 \leq p \leq m$）的 按位或（OR） 结果必须不超过数字 $k$。
• 所有选中的 $b_{i_p}$（$1 \leq p \leq m$）的总和是 最大 的。

按位或（记为 $|$）——一种对每个比特位执行的操作，仅当两个数的对应比特位都为 $0$ 时，结果位才是 $0$。否则，结果位为 $1$。考虑两个数字 $9$ 和 $10$ 的例子。它们的二进制表示分别是 $1001$ 和 $1010$（不考虑高位为 $0$ 的位）。然后对每个比特位应用 OR 操作。因此，第零位是 $(1|0)$，等于 $1$。第一位是 $(0|1)$，也等于 $1$。第二位是 $(0|0) = 0$，第三位是 $(1|1) = 1$。因此，数字 $9$ 和 $10$ 的按位或在二进制下表示为 $1011$，等于 $11$。

女士在寻找最 优美 集合时遇到了问题。她明白寻找这个集合是件困难的事，所以只请你告诉她最 优美 集合中所有 $b_{i_p}$ 的总和。

输入格式

第一行包含两个整数 $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}$)。

输出格式

输出一个数字 —— 所选 $b_{i_p}$ 的最大可能总和。

3 10
5 1
3 1
10 1

2

4 12
8 3
6 2
1 2
5 2

6

提示

样例说明

在第一个样例中，如果选择第一对和第二对作为答案，则得到的按位或结果为 $7$，所求总和为 $2$。无法再增加总和，因为如果选择全部三对，得到的按位或结果为 $15$，超过了 $k$。

在第二个样例中，最优方案是选择第二、第三和第四对，得到答案 $6$。如果选择第一对，那么为了使得按位或结果不超过 $k$，只能再选择第三对。因此最大可能总和为 $6$。

评分细则

• （17 分）： $n \leq 10$；
• （26 分）： $n \leq 10^4$, $k < 2^{10}$；
• （14 分）： $k = 2^t - 1$，其中 $0 \leq t \leq 30$；
• （43 分）： 无额外限制。

翻译由 DeepSeek V3 完成