P15028 [UOI 2021 II Stage] 献给女士的礼物

哥萨克胡子想了很久，在女士生日那天送她什么礼物。他决定送一件既独特又最重要的——是有用的礼物。于是，哥萨克胡子送给女士一套由 $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}$ 的最大可能总和。

### 样例说明 在第一个样例中，如果选择第一对和第二对作为答案，则得到的按位或结果为 $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 完成