问题陈述

开始时有一个非负整数 $X$，其初始值等于 $S$。可以按任意顺序、任意次数执行以下操作：

• 将 $X$ 加 $1$，花费为 $A$。
• 选择 $i$ 在 $1$ 到 $N$ 之间，并将 $X$ 替换为 $X \\oplus Y_i$，花费为 $C_i$。其中，$\\oplus$ 表示按位异或运算。

找到使得 $X$ 等于给定的非负整数 $T$ 的最小总花费，如果不可能，则报告无法达成。

什么是按位异或运算？

非负整数 $A$ 和 $B$ 的按位异或运算 $A \\oplus B$ 定义如下：

• 当 $A \\oplus B$ 以二进制表示时，$2^k$ 位（$k \\geq 0$）的数字是 $1$，当且仅当 $A$ 和 $B$ 在该位上的数字中只有一个为 $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)$ 被定义为不依赖于 $p_1, p_2, p_3, \\dots, p_k$ 的顺序。我们可以证明这个值不依赖于 $p_1, p_2, p_3, \\dots, p_k$ 的顺序。

约束条件

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

1 15 0 1
8 2

示例输出 1

5

可以按以下方式使 $X$ 等于 $T$：

• 选择 $i=1$，将 $X$ 替换为 $X \\oplus 8$，得到 $X=7$。花费为 $2$。
• 将 $1$ 加到 $X$，得到 $X=8$。花费为 $1$。
• 选择 $i=1$，将 $X$ 替换为 $X \\oplus 8$，得到 $X=0$。花费为 $2$。

---

示例输入 2

3 21 10 100
30 1
12 1
13 1

示例输出 2

3

---

示例输入 3

1 2 0 1
1 1

示例输出 3

-1

---

示例输入 4

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

示例输出 4

563645