Description

给出两个序列，每个序列包含 $N$ 个整数： $A = (A_1, A_2, \ldots, A_N)$ 和 $B = (B_1, B_2, \ldots, B_N)$ 。

在序列 $A$ 中，可以按任意顺序进行下面的两次运算(可能为零)。

• 选择一个满足 $1 \leq i \leq N$ 的整数 $i$ ，并将 $A_i$ 增加或减少 $1$ ，费用为 $X$ 日元(日币)。
• 选择满足 $1 \leq i \leq N-1$ 的整数 $i$ ，并交换 $A_i$ 和 $A_{i+1}$ 的值，代价是 $Y$ 日元。

重复上述步骤，打印出使序列 $A$ 等于序列 $B$ 所需的最小总成本。

Format

Input

第一行输入三个空格隔开的整数 $N,X,Y$

接下来一行输入 $N$ 个空格隔开的整数代表 $A_1,A_2,\cdots,A_N$

接下来一行输入 $N$ 个空格隔开的整数代表 $B_1,B_2,\cdots,B_N$

Output

打印使 $A$ 等于 $B$ 所需的最小总成本。

Samples

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

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

这些操作的总成本为 $3+5+5+3 = 16$ 日元，是可能的最小值。

Limitation

• $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$
• 所有输入值均为整数。