AT_abc232_f [ABC232F] Simple Operations on Sequence

给定两个长度为 $N$ 的整数序列 $A = (A_1, A_2, \ldots, A_N)$ 和 $B = (B_1, B_2, \ldots, B_N)$。 对于整数序列 $A$，你可以任意次数（可以为 $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$ 所需的最小总费用。

## 限制条件 - $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$ - 所有输入均为整数 ## 样例解释 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$ 日元，这是最小值。 ## 样例解释 2 $A$ 和 $B$ 从一开始就完全一致，因此无需进行任何操作。 ## 样例解释 3 请注意，输入或输出可能超出 $32$ 位整数范围。 由 ChatGPT 4.1 翻译