Score : $600$ points

问题描述

有 $N$ 张卡片，编号分别为 $1, \dots, N$。第 $i$ 张卡片（$1 \leq i \leq N$）正面写有一个整数 $A_i$，背面写有一个整数 $B_i$。

考虑选择一个或多个卡片，使得所选卡片正面整数的按位异或和不大于 $K$。求所选卡片背面整数的最大可能按位异或和。

什么是按位异或和？两个整数 $a$ 和 $b$ 的按位异或和（exclusive logical sum）$a \oplus b$ 定义如下：

• 在二进制表示中，若 $a$ 和 $b$ 的 $2^k$ 位（$k \geq 0$）中恰好有一个为 $1$，则 $a \oplus 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$ 的顺序无关。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There are $N$ cards numbered $1, \dots, N$. Card $i \, (1 \leq i \leq N)$ has an integer $A_i$ written on the front and an integer $B_i$ written on the back.

Consider choosing one or more cards so that the exclusive logical sum of the integers written on the front of the chosen cards is at most $K$. Find the maximum possible exclusive logical sum of the integers written on the back of the chosen cards.

What is the exclusive logical sum? The exclusive logical sum $a \oplus b$ of two integers $a$ and $b$ is defined as follows.

• The $2^k$'s place ($k \geq 0$) in the binary notation of $a \oplus b$ is $1$ if exactly one of the $2^k$'s places in the binary notation of $a$ and $b$ is $1$; otherwise, it is $0$.

For example, $3 \oplus 5 = 6$ (In binary notation: $011 \oplus 101 = 110$).
In general, the exclusive logical sum of $k$ integers $p_1, \dots, p_k$ is defined as $(\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k)$. We can prove that it is independent of the order of $p_1, \dots, p_k$.

Constraints

• $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)$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $K$

$A_1$ $B_1$

$\vdots$

$A_N$ $B_N$

Output

Print the maximum possible exclusive logical sum of the integers written on the back of the chosen cards when choosing one or more cards so that the exclusive logical sum of the integers written on the front of the chosen cards is at most $K$. If it is impossible to choose cards in such way, print $-1$ instead.

Sample Input 1

4 2
1 1
3 2
2 2
0 1

Sample Output 1

3

By choosing Cards $1$ and $2$, the exclusive logical sum of the integers written on the front of them is $2$, and that on the back of them is $3$, which is the maximum.

Sample Input 2

1 2
3 4

Sample Output 2

-1

It is impossible to choose cards so that the condition is satisfied.

Sample Input 3

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

Sample Output 3

1064164329

update @ 2024/3/10 10:39:54