AT_abc328_g [ABC328G] Cut and Reorder

[problemUrl]: https://atcoder.jp/contests/abc328/tasks/abc328_g 長さ $ N $ の数列 $ A=(A\ _\ 1,A\ _\ 2,\ldots,A\ _\ N),B=(B\ _\ 1,B\ _\ 2,\ldots,B\ _\ N) $ が与えられます。 あなたは、数列 $ A $ に対して次の $ 2 $ 種類の操作を好きな順番で好きな回数行うことができます。 - $ A $ を好きな位置で分割し、分割された列を自由に並べ替える。分割した位置 $ 1 $ つにつきコストが $ C $ かかる。 厳密には、$ (X-1)C $ のコストをかけて長さ $ X+1 $ の列 $ (i\ _\ 0,i\ _\ 1,i\ _\ 2,\ldots,i\ _\ X)\ (0=i\ _\ 0\lt\ i\ _\ 1\lt\ i\ _\ 2\lt\cdots\lt\ i\ _\ X=N) $ と $ (1,2,\ldots,X) $ の順列 $ p $ を自由にとり、$ (A\ _\ {i\ _\ {p\ _\ j-1}+1},A\ _\ {i\ _\ {p\ _\ j-1}+2},\ldots,A\ _\ {i\ _\ {p\ _\ j}}) $ を $ j $ の昇順に連結したものを新しい $ A $ とする。 - 整数 $ k $ と $ A $ の好きな要素を $ 1 $ つ選び、選んだ要素の値に $ k $ を加える。コストが $ |k| $ かかる。 操作をすべて終えたときに $ A $ と $ B $ が等しくなるように操作を行うとき、必要なコストの合計の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ C $ $ A\ _\ 1 $ $ A\ _\ 2 $ $ \ldots $ $ A\ _\ N $ $ B\ _\ 1 $ $ B\ _\ 2 $ $ \ldots $ $ B\ _\ N $

答えを出力せよ。

### 制約 - $ 1\leq\ N\leq22 $ - $ 1\leq\ C\leq10^{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) $ - 入力はすべて整数 ### Sample Explanation 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 $ と出力してください。 ### Sample Explanation 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 $ と出力してください。 ### Sample Explanation 3 入力や答えが $ 32\operatorname{bit} $ 整数に収まらない場合があります。