{"raw_statement":[{"iden":"problem statement","content":"There is a non-negative integer $X$ initially equal to $S$. One can perform the following operations, in any order, any number of times:\n\n*   Add $1$ to $X$. This has a cost of $A$.\n*   Choose $i$ between $1$ and $N$, and replace $X$ with $X \\oplus Y_i$. This has a cost of $C_i$. Here, $\\oplus$ denotes bitwise $\\mathrm{XOR}$.\n\nFind the smallest total cost to make $X$ equal to a given non-negative integer $T$, or report that this is impossible.\nWhat is bitwise $\\mathrm{XOR}$?The bitwise $\\mathrm{XOR}$ of non-negative integers $A$ and $B$, $A \\oplus B$, is defined as follows:\n\n*   When $A \\oplus B$ is written in base two, the digit in the $2^k$'s place ($k \\geq 0$) is $1$ if exactly one of the digits in that place of $A$ and $B$ is $1$, and $0$ otherwise.\n\nFor example, we have $3 \\oplus 5 = 6$ (in base two: $011 \\oplus 101 = 110$).  \nGenerally, the bitwise $\\mathrm{XOR}$ of $k$ non-negative integers $p_1, p_2, p_3, \\dots, p_k$ is defined as $(\\dots ((p_1 \\oplus p_2) \\oplus p_3) \\oplus \\dots \\oplus p_k)$. We can prove that this value does not depend on the order of $p_1, p_2, p_3, \\dots, p_k$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 8$\n*   $0 \\leq S, T < 2^{40}$\n*   $0 \\leq A \\leq 10^5$\n*   $0 \\leq Y_i < 2^{40}$ ($1 \\leq i \\leq N$)\n*   $0 \\leq C_i \\leq 10^{16}$ ($1 \\leq i \\leq N$)\n*   All values in the input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $S$ $T$ $A$\n$Y_1$ $C_1$\n$\\vdots$\n$Y_N$ $C_N$"},{"iden":"sample input 1","content":"1 15 0 1\n8 2"},{"iden":"sample output 1","content":"5\n\nYou can make $X$ equal to $T$ in the following manner:\n\n*   Choose $i=1$ and replace $X$ with $X \\oplus 8$ to get $X=7$. This has a cost of $2$.\n*   Add $1$ to $X$ to get $X=8$. This has a cost of $1$.\n*   Choose $i=1$ and replace $X$ with $X \\oplus 8$ to get $X=0$. This has a cost of $2$."},{"iden":"sample input 2","content":"3 21 10 100\n30 1\n12 1\n13 1"},{"iden":"sample output 2","content":"3"},{"iden":"sample input 3","content":"1 2 0 1\n1 1"},{"iden":"sample output 3","content":"\\-1"},{"iden":"sample input 4","content":"8 352217 670575 84912\n239445 2866\n537211 16\n21812 6904\n50574 8842\n380870 5047\n475646 8924\n188204 2273\n429397 4854"},{"iden":"sample output 4","content":"563645"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}