配点 : $500$ 点

問題文

長さ $N$ の $2$ つの整数列 $A = (A_1, A_2, \ldots, A_N)$ および $B = (B_1, B_2 \ldots, B_N)$ が与えられます。

整数列 $A$ に対して、「下記の $2$ つの操作のうちどちらかを行う」ということを好きな回数（ $0$ 回でもよい）繰り返すことができます。

• $1 \leq i \leq N$ を満たす整数 $i$ を選び、$A_i$ の値を $1$ 増やすか $1$ 減らす。この操作には $X$ 円の費用がかかる。
• $1 \leq i \leq N-1$ を満たす整数 $i$ を選び、$A_i$ の値と $A_{i+1}$ の値を入れ替える。この操作には $Y$ 円の費用がかかる。

上記の繰り返しによって整数列 $A$ を整数列 $B$ に一致させるためにかかる合計費用としてあり得る最小値を出力してください。

制約

• $2 \leq N \leq 18$
• $1 \leq X \leq 10^8$
• $1 \leq Y \leq 10^{16}$
• $1 \leq A_i, B_i \leq 10^8$
• 入力はすべて整数

入力

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

$N$ $X$ $Y$

$A_1$ $A_2$ $\ldots$ $A_N$

$B_1$ $B_2$ $\ldots$ $B_N$

出力

$A$ を $B$ に一致させるためにかかる合計費用としてあり得る最小値を求めよ。

4 3 5
4 2 5 2
6 4 2 1

16

はじめ、$A = (4, 2, 5, 2)$ です。 下記の通りに操作を行うと、$A$ を $B$ に一致させることができます。

• $X = 3$ 円払い、$A_3$ の値を $1$ 増やす。その結果 $A = (4, 2, 6, 2)$ となる。
• $Y = 5$ 円払い、$A_2$ の値と $A_3$ の値を入れ替える。その結果 $A = (4, 6, 2, 2)$ となる。
• $Y = 5$ 円払い、$A_1$ の値と $A_2$ の値を入れ替える。その結果 $A = (6, 4, 2, 2)$ となる。
• $X = 3$ 円払い、$A_4$ の値を $1$ 減らす。その結果 $A = (6, 4, 2, 1) = B$ となる。

上記の操作にかかる費用の合計は $3+5+5+3 = 16$ 円であり、これが最小となります。

5 12345 6789
1 2 3 4 5
1 2 3 4 5

0

$A$ と $B$ は初めから一致しているため、一度も操作を行う必要がありません。

18 20719114 5117250357733867
10511029 36397527 63027379 44706927 47672230 79861204 57882493 42931589 51053644 52300688 43971370 26515475 62139996 41282303 34022578 12523039 6696497 64922712
14720753 4621362 25269832 91410838 86751784 32741849 6602693 60719353 28911226 88280613 18745325 80675202 34289776 37849132 99280042 73760634 43897718 40659077

13104119429316474

入力や出力が $32$ bit 整数型に収まらないことがあることに注意してください。