题目描述

有 $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$），如果 $a$ 和 $b$ 的 $2^k$ 位中恰好有一个位是 $1$，则 $a \oplus b$ 的该位为 $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$ 的顺序无关。

约束条件

• $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)$
• 输入的所有值都是整数。

输入

输入数据从标准输入获得，格式如下：

$N$ $K$ $A_1$ $B_1$ $\vdots$ $A_N$ $B_N$

输出

打印选择一张或多张卡片，使得所选卡片正面的整数异或和不超过 $K$ 的条件下，背面整数的最大可能异或和。如果无法按照条件选择卡片，则输出 $-1$。

示例输入 1

4 2
1 1
3 2
2 2
0 1

示例输出 1

3

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

示例输入 2

1 2
3 4

示例输出 2

-1

无法满足条件选择卡片的情况。

示例输入 3

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

示例输出 3

1064164329