{"problem":{"name":"Increment or XOR","description":{"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: *   Add $1$ to $X$. This has a cost of $A$. *   Choose $i$ bet","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc061_e"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc061_e","tags":[],"sample_group":[["1 15 0 1\n8 2","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$."],["3 21 10 100\n30 1\n12 1\n13 1","3"],["1 2 0 1\n1 1","\\-1"],["8 352217 670575 84912\n239445 2866\n537211 16\n21812 6904\n50574 8842\n380870 5047\n475646 8924\n188204 2273\n429397 4854","563645"]],"created_at":"2026-03-03 11:01:14"}}