Xor Cards

题目描述

有 $N$ 张编号为 $1, \dots, N$ 的卡片。卡片 $i \, (1 \leq i \leq N)$ 的正面写有一个整数 $A_i$，背面写有一个整数 $B_i$。 考虑选择一个或多个卡片，使得被选择的卡片正面所写整数的按位异或之和不超过 $K$。求被选择的卡片背面所写整数的按位异或之和的最大可能值。

输入格式

输入按下述格式从标准输入给出： $N$ $K$ $A_1$ $B_1$ $\vdots$ $A_N$ $B_N$

输出格式

当选择一个或多个卡片使得被选择的卡片正面所写整数的按位异或之和不超过 $K$ 时，输出被选择的卡片背面所写整数的按位异或之和的最大可能值。如果不存在满足条件的选法，则输出 $-1$。

4 2
1 1
3 2
2 2
0 1

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)$ 输入中的所有值均为整数。选择第 $1$ 和第 $2$ 张卡片时，它们正面所写整数的按位异或为 $2$，背面所写整数的按位异或为 $3$，这是最大值。
不存在满足条件的卡片选择方法。

标签: AtCoder|abc249G

来源

AtCoder|abc249G