E - Increment or XOR Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1400 点

問題文

非負整数 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 の順番によらないことが証明できます。

制約

  • 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 である。
  • X に 1 を足し、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

Score : 1400 points

Problem Statement

There is a non-negative integer X initially equal to S. One can perform the following operations, in any order, any number of times:

  • Add 1 to X. This has a cost of A.
  • Choose i between 1 and N, and replace X with X \oplus Y_i. This has a cost of C_i. Here, \oplus denotes bitwise \mathrm{XOR}.

Find the smallest total cost to make X equal to a given non-negative integer T, or report that this is impossible.

What is bitwise \mathrm{XOR}?

The bitwise \mathrm{XOR} of non-negative integers A and B, A \oplus B, is defined as follows:

  • When A \oplus B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if exactly one of the digits in that place of A and B is 1, and 0 otherwise.
For example, we have 3 \oplus 5 = 6 (in base two: 011 \oplus 101 = 110).
Generally, the bitwise \mathrm{XOR} of k non-negative integers p_1, p_2, p_3, \dots, p_k is defined as (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k). We can prove that this value does not depend on the order of p_1, p_2, p_3, \dots, p_k.

Constraints

  • 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)
  • All values in the input are integers.

Input

Input is given from Standard Input in the following format:

N S T A
Y_1 C_1
\vdots
Y_N C_N

Output

If the task is impossible, print -1. Otherwise, print the smallest total cost.

Sample Input 1

1 15 0 1
8 2

Sample Output 1

5

You can make X equal to T in the following manner:

  • Choose i=1 and replace X with X \oplus 8 to get X=7. This has a cost of 2.
  • Add 1 to X to get X=8. This has a cost of 1.
  • Choose i=1 and replace X with X \oplus 8 to get X=0. This has a cost of 2.

Sample Input 2

3 21 10 100
30 1
12 1
13 1

Sample Output 2

3

Sample Input 3

1 2 0 1
1 1

Sample Output 3

-1

Sample Input 4

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

Sample Output 4

563645