题目描述

有一个非负整数 $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

输入

1 15 0 1
8 2

输出

5

样例 2

输入

3 21 10 100
30 1
12 1
13 1

输出

3

样例 3

输入

1 2 0 1
1 1

输出

-1

样例 4

输入

8 352217 670575 84912
239445 2866
537211 16
21812 6904
50574 8842
380870 5047
475646 8924
188204 2273
429397 4854

输出

563645

说明/提示

限制条件

• $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 翻译