Contest Duration: - (local time) (100 minutes) Back to Home
G - Xor Cards /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

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

• a \oplus b を二進表記した際の 2^k \, (k \geq 0) の位の数は、a, b を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。

### 制約

• 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


### 出力例 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.
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