配点 : $1400$ 点

問題文

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

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

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

制約

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

入力

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

$N$ $S$ $T$ $A$

$Y_1$ $C_1$

$\vdots$

$Y_N$ $C_N$

出力

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

1 15 0 1
8 2

5

以下の方法で $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$ である。

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