← 返回题目列表

AtCoder · agc061_e

E. 增量或异或

中文机器翻译题面 查看原题

分数: 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 否则。
例如,我们有 3 \oplus 5 = 6 (以二为基数: 011 \oplus 101 = 110).
一般来说,按位 \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