/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
N 枚のカードがあり、1, \dots, N の番号が付けられています。カード i \, (1 \leq i \leq N) の表には整数 A_i、裏には整数 B_i が書かれています。
選んだカードの表に書かれた整数の排他的論理和が K 以下となるように 1 枚以上の好きな枚数のカードを選ぶとき、選んだカードの裏に書かれた整数の排他的論理和としてあり得る最大値を求めてください。
排他的論理和とは
整数 a, b の排他的論理和 a \oplus b は、以下のように定義されます。- a \oplus b を二進表記した際の 2^k \, (k \geq 0) の位の数は、a, b を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
一般に 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
出力
問題文中の条件を満たすようにカードを選ぶとき、選んだカードの裏に書かれた整数の排他的論理和としてあり得る最大値を出力せよ。ただし、条件を満たすようにカードを選ぶことができないときは -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
Score : 600 points
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.
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