AT_agc061_e [AGC061E] Increment or XOR

有一个非负整数 $X$，初始值为 $S$。你可以以任意顺序、任意次数执行以下操作： - 给 $X$ 加 $1$。该操作的代价为 $A$。 - 选择一个 $1$ 到 $N$ 之间的 $i$，将 $X$ 替换为 $X \oplus Y_i$。该操作的代价为 $C_i$。这里，$\oplus$ 表示按位异或运算。 请你求出将 $X$ 变为给定非负整数 $T$ 所需的最小总代价，或者报告无法达成目标。 按位异或运算的定义如下： 对于非负整数 $A, B$，$A \oplus B$ 的二进制表示中，第 $2^k$ 位（$k \geq 0$）的数，如果 $A$ 和 $B$ 的该位只有一个为 $1$，则结果为 $1$，否则为 $0$。 例如，$3 \oplus 5 = 6$（二进制为：$011 \oplus 101 = 110$）。 一般地，$k$ 个非负整数 $p_1, p_2, p_3, \dots, p_k$ 的按位异或为 $(\dots((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k)$，并且可以证明，这个结果与顺序无关。

输入从标准输入读入，格式如下： > $N$ $S$ $T$ $A$ > $Y_1$ $C_1$ > $\vdots$ > $Y_N$ $C_N$

如果无法达成目标，输出 `-1`。否则，输出所需的最小总代价。

### 限制条件 - $1 \leq N \leq 8$ - $0 \leq S, T < 2^{40}$ - $0 \leq A \leq 10^5$ - $0 \leq Y_i < 2^{40}$（$1 \leq i \leq N$） - $0 \leq C_i \leq 10^{16}$（$1 \leq i \leq N$） - 输入中的所有值均为整数。 ### 样例解释 1 可以通过以下方式将 $X$ 变为 $T$： - 选择 $i=1$，将 $X$ 替换为 $X \oplus 8$，此时 $X=7$，代价为 $2$。 - 给 $X$ 加 $1$，此时 $X=8$，代价为 $1$。 - 选择 $i=1$，将 $X$ 替换为 $X \oplus 8$，此时 $X=0$，代价为 $2$。 由 ChatGPT 4.1 翻译