AT_abc232_f [ABC232F] Simple Operations on Sequence

[problemUrl]: https://atcoder.jp/contests/abc232/tasks/abc232_f 長さ $ N $ の $ 2 $ つの整数列 $ A\ =\ (A_1,\ A_2,\ \ldots,\ A_N) $ および $ B\ =\ (B_1,\ B_2\ \ldots,\ B_N) $ が与えられます。 整数列 $ A $ に対して、「下記の $ 2 $ つの操作のうちどちらかを行う」ということを好きな回数（ $ 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 $ - 入力はすべて整数 ### Sample Explanation 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 $ 円であり、これが最小となります。 ### Sample Explanation 2 $ A $ と $ B $ は初めから一致しているため、一度も操作を行う必要がありません。 ### Sample Explanation 3 入力や出力が $ 32 $ bit 整数型に収まらないことがあることに注意してください。