序列上的简单操作

题目描述

给定两个各含 $N$ 个整数的序列:$A = (A_1, A_2, \ldots, A_N)$ 和 $B = (B_1, B_2, \ldots, B_N)$。

你可以对序列 $A$ 任意多次(可以为 $0$ 次)按任意顺序进行下面两种操作。

• 选择满足 $1 \le i \le N$ 的整数 $i$,将 $A_i$ 加 $1$ 或减 $1$,花费 $X$ 日元。
• 选择满足 $1 \le i \le 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$ 所需的最小总花费。

样例

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)$。

这些操作的总花费为 $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$ 位整数范围。

数据范围

• $2 \le N \le 18$
• $1 \le X \le 10^8$
• $1 \le Y \le 10^{16}$
• $1 \le A_i, B_i \le 10^8$
• 输入均为整数