异或卡片

题目描述

有 $N$ 张卡片,编号为 $1, \dots, N$。第 $i$ 张卡片 $(1 \leq i \leq N)$ 的正面写着整数 $A_i$,背面写着整数 $B_i$。

考虑选择一张或多张卡片,使得所选卡片正面所写整数的异或和至多为 $K$。求所选卡片背面所写整数的异或和的最大可能值。

什么是异或和?

两个整数 $a$ 和 $b$ 的异或 $a \oplus b$ 定义如下。

在 $a \oplus b$ 的二进制表示中,$2^k$ 位($k \geq 0$)上的值为 $1$,当且仅当 $a$ 和 $b$ 的二进制表示中 $2^k$ 位上的值恰好有一个为 $1$;否则为 $0$。

例如,$3 \oplus 5 = 6$(二进制表示:$011 \oplus 101 = 110$)。

一般地,$k$ 个整数 $p_1, \dots, p_k$ 的异或和定义为 $(\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k)$。可以证明它与 $p_1, \dots, p_k$ 的顺序无关。

输入格式

输入按以下格式从标准输入给出:

N K
A_1 B_1
⋮
A_N B_N

输出格式

在「选择一张或多张卡片,使得所选卡片正面整数的异或和至多为 $K$」的前提下,输出所选卡片背面整数的异或和的最大可能值。若不存在满足条件的选法,则输出 $-1$。

样例

4 2
1 1
3 2
2 2
0 1

3

选择卡片 $1$ 和 $2$ 时,正面整数的异或和为 $2$,背面整数的异或和为 $3$,这是最大值。

1 2
3 4

-1

不存在满足条件的选法。

10 326872757
487274679 568989827
267359104 968688210
669234369 189421955
1044049637 253386228
202278801 233212012
436646715 769734012
478066962 376960084
491389944 1033137442
214977048 1051768288
803550682 1053605300

1064164329

数据范围

• $1 \leq N \leq 1000$
• $0 \leq K \lt 2^{30}$
• $0 \leq A_i, B_i \lt 2^{30} \, (1 \leq i \leq N)$
• 输入中的所有值都是整数。