{"raw_statement":[{"iden":"problem statement","content":"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.\nConsider 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.\nWhat is the exclusive logical sum? The exclusive logical sum $a \\oplus b$ of two integers $a$ and $b$ is defined as follows.\n\n*   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$.\n\nFor example, $3 \\oplus 5 = 6$ (In binary notation: $011 \\oplus 101 = 110$).  \nIn 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$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 1000$\n*   $0 \\leq K \\lt 2^{30}$\n*   $0 \\leq A_i, B_i \\lt 2^{30} \\, (1 \\leq i \\leq N)$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $K$\n$A_1$ $B_1$\n$\\vdots$\n$A_N$ $B_N$"},{"iden":"sample input 1","content":"4 2\n1 1\n3 2\n2 2\n0 1"},{"iden":"sample output 1","content":"3\n\nBy 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."},{"iden":"sample input 2","content":"1 2\n3 4"},{"iden":"sample output 2","content":"\\-1\n\nIt is impossible to choose cards so that the condition is satisfied."},{"iden":"sample input 3","content":"10 326872757\n487274679 568989827\n267359104 968688210\n669234369 189421955\n1044049637 253386228\n202278801 233212012\n436646715 769734012\n478066962 376960084\n491389944 1033137442\n214977048 1051768288\n803550682 1053605300"},{"iden":"sample output 3","content":"1064164329"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}