分数: 1400 点
问题陈述
有一个非负整数 X 最初等于 S。可以以任意顺序、任意次数执行以下操作:
- 添加 1 to X。这需要花费 A.
- 选择 i 之间 1 和 N,并替换 X 与 X \oplus Y_i。这需要花费 C_i。在这里, \oplus 表示按位 \mathrm{XOR}.
找出最小的总成本 X 等于给定的非负整数 T,或报告这是不可能的。
什么是按位 \mathrm{XOR}?
按位 \mathrm{XOR} 非负整数 A 和 B, A \oplus B,定义如下:
- 当 A \oplus B 以基数 2 书写,即 2^k的地点 (k \geq 0)是 1 如果恰好是该位置的数字之一 A 和 B is 1,和 0 否则。
一般来说,按位 \mathrm{XOR} of 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.
约束
- 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 to 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