题目描述

非負整数 $X$ があり、はじめその値は $S$ です。以下の操作を任意の順に何度でも行うことができます。

• $X$ に $1$ を足す。この操作のコストは $A$ である。
• $1$ 以上 $N$ 以下の $i$ を選び、$X$ を $X\ \oplus\ Y_i$ に置き換える。この操作のコストは $C_i$ である。ここで、$\oplus$ はビット単位 $\mathrm{XOR}$ 演算を表す。

与えられた非負整数 $T$ に $X$ を等しくするのに必要な最小の合計コストを求めるか、それが不可能であることを報告してください。

ビット単位 $\mathrm{XOR}$ 演算とは 非負整数 $A,\ B$ のビット単位 $\mathrm{XOR}$、$A\ \oplus\ B$ は、以下のように定義されます。

• $A\ \oplus\ B$ を二進表記した際の $2^k$ ($k\ \geq\ 0$) の位の数は、$A,\ B$ を二進表記した際の $2^k$ の位の数のうち一方のみが $1$ であれば $1$、そうでなければ $0$ である。

例えば、$3\ \oplus\ 5\ =\ 6$ となります（二進表記すると: $011\ \oplus\ 101\ =\ 110$）。
一般に、$k$ 個の非負整数 $p_1,\ p_2,\ p_3,\ \dots,\ p_k$ のビット単位 $\mathrm{XOR}$ は $ (\dots\ ((p_1\ \oplus\ p_2)\ \oplus\ p_3)\ \oplus\ \dots\ \oplus\ p_k) $ と定義され、これは $p_1,\ p_2,\ p_3,\ \dots,\ p_k$ の順番によらないことが証明できます。

输入格式

入力は、標準入力から以下の形式で与えられる。

$N$ $S$ $T$ $A$ $Y_1$ $C_1$ $\vdots$ $Y_N$ $C_N$

输出格式

課題が達成不可能なら、-1 を出力せよ。 そうでないなら、必要な最小の合計コストを出力せよ。

题目大意

你有一个非负整数 $X$ 初始为 $S$。给定 $N$ 和数列 $Y_1,Y_2,\dots Y_N$ 以及 $C_1,C_2,\dots,C_N$。你可以进行下列操作任意多次：

• 令 $X\gets X+1$，花费 $A$ 的代价；
• 令 $X\gets X\operatorname{xor} Y_i$，花费 $C_i$ 的代价。

你想要把 $S$ 变成 $T$，求最小代价。

$1\le N\le 8,0\le S,T,Y_i<2^{40},0\le A\le 10^5,0\le C_i\le 10^{16}.$

1 15 0 1
8 2

5

3 21 10 100
30 1
12 1
13 1

3

1 2 0 1
1 1

-1

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$)
• 入力中の値は全て整数である。

Sample Explanation 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$ である。