配点 : $600$ 点

問題文

$N$ 枚のカードがあり、$1, \dots, N$ の番号が付けられています。カード $i \, (1 \leq i \leq N)$ の表には整数 $A_i$、裏には整数 $B_i$ が書かれています。

選んだカードの表に書かれた整数の排他的論理和が $K$ 以下となるように $1$ 枚以上の好きな枚数のカードを選ぶとき、選んだカードの裏に書かれた整数の排他的論理和としてあり得る最大値を求めてください。

制約

• $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$

出力

問題文中の条件を満たすようにカードを選ぶとき、選んだカードの裏に書かれた整数の排他的論理和としてあり得る最大値を出力せよ。ただし、条件を満たすようにカードを選ぶことができないときは $-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