问题描述

给定两个长度均为 $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$ 所需的最小总花费。

约束条件

• $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$ 所需的最小总花费。

示例输入 1

4 3 5
4 2 5 2
6 4 2 1

示例输出 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$ 日元，是可能的最小值。

示例输入 2

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

示例输出 2

0

$A$ 和 $B$ 从一开始就相等，因此不需要任何操作。

示例输入 3

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

示例输出 3

13104119429316474

注意，输入或输出的值可能无法适应 $32$ 位整数类型。