AT_abc328_g [ABC328G] Cut and Reorder

给定长度为 $N$ 的数列 $A=(A_1,A_2,\ldots,A_N)$ 和 $B=(B_1,B_2,\ldots,B_N)$。 你可以对数列 $A$ 进行如下两种操作，操作的顺序和次数均不限： - 可以在任意位置将 $A$ 分割，并将分割后的各段自由重新排列。每分割一次（即每增加一个分割点）需要花费 $C$ 的代价。具体来说，花费 $(X-1)C$ 的代价，可以任选一个长度为 $X+1$ 的分割点序列 $(i_0,i_1,i_2,\ldots,i_X)\ (0=i_0

输入以如下格式从标准输入读入： > $N$ $C$ $A_1$ $A_2$ $\ldots$ $A_N$ $B_1$ $B_2$ $\ldots$ $B_N$

请输出答案。

## 限制条件 - $1\leq N\leq 22$ - $1\leq C\leq 10^{15}$ - $1\leq A_i\leq 10^{15}\ (1\leq i\leq N)$ - $1\leq B_i\leq 10^{15}\ (1\leq i\leq N)$ - 输入均为整数 ## 样例解释 1 例如，可以通过如下操作使 $A$ 和 $B$ 相等： - 给 $A_2$ 加上 $2$，花费 $2$，$A=(3,3,4,1,5)$。 - 给 $A_4$ 加上 $1$，花费 $1$，$A=(3,3,4,2,5)$。 - 给 $A_3$ 加上 $3$，花费 $3$，$A=(3,3,7,2,5)$。 - 将 $A$ 分割为 $(3,3)$ 和 $(7,2,5)$，并交换顺序，花费 $1$，$A=(7,2,5,3,3)$。 - 给 $A_3$ 加上 $1$，花费 $1$，$A=(7,2,6,3,3)$。 - 给 $A_4$ 加上 $2$，花费 $2$，$A=(7,2,6,5,3)$。 - 给 $A_1$ 加上 $2$，花费 $2$，$A=(9,2,6,5,3)$。 总代价为 $2+1+3+1+1+2+2=12$。无法用 $11$ 或更少的代价使 $A$ 和 $B$ 相等，因此输出 $12$。 ## 样例解释 2 例如，可以通过如下操作使 $A$ 和 $B$ 相等： - 给 $A_1$ 加上 $6$，花费 $6$，$A=(9,1,4,1,5)$。 - 给 $A_2$ 加上 $1$，花费 $1$，$A=(9,2,4,1,5)$。 - 给 $A_3$ 加上 $2$，花费 $2$，$A=(9,2,6,1,5)$。 - 给 $A_4$ 加上 $4$，花费 $4$，$A=(9,2,6,5,5)$。 - 给 $A_5$ 加上 $-2$，花费 $2$，$A=(9,2,6,5,3)$。 总代价为 $15$。无法用 $14$ 或更少的代价使 $A$ 和 $B$ 相等，因此输出 $15$。 ## 样例解释 3 输入和答案可能超出 $32\operatorname{bit}$ 整数范围。 由 ChatGPT 4.1 翻译