题目描述

長さ $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$ に一致させるためにかかる合計費用としてあり得る最小値を出力してください。

输入格式

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

$N$ $X$ $Y$ $A_1$ $A_2$ $\ldots$ $A_N$ $B_1$ $B_2$ $\ldots$ $B_N$

输出格式

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

题目大意

给出正整数数列 $A_1,A_2,\cdots,A_n$ 和 $B_1,B_2,\cdots,B_n$。

有两种操作：

• 花费 $X$，把 $A$ 中一个数加一或减一；

• 花费 $Y$，交换 $A$ 中两个相邻元素。

求 $A$ 变为 $B$ 所需的最小代价。

4 3 5
4 2 5 2
6 4 2 1

16

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

0

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

提示

制約

• $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$
• 入力はすべて整数

Sample Explanation 1

はじめ、$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$ 円であり、これが最小となります。

Sample Explanation 2

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

Sample Explanation 3

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