AT_abc290_h [ABC290Ex] Bow Meow Optimization

[problemUrl]: https://atcoder.jp/contests/abc290/tasks/abc290_h $ 1 $ から $ N $ までの番号がついた $ N $ 匹の犬と、$ 1 $ から $ M $ までの番号がついた $ M $ 匹の猫がいます。 今から、これらの $ N+M $ 匹を左右一列に好きな順序で並べます。 並べ方に応じて、それぞれの犬と猫には以下のように*不満度*が生じます。 - 犬 $ i $ の不満度は、その犬より左にいる猫の匹数を $ x $、右にいる猫の匹数を $ y $ とすると、$ A_i\times|x-y| $ である。 - 猫 $ i $ の不満度は、その猫より左にいる犬の匹数を $ x $、右にいる犬の匹数を $ y $ とすると、$ B_i\times|x-y| $ である。 不満度の総和の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ B_1 $ $ B_2 $ $ \ldots $ $ B_M $

答えを整数として出力せよ。

### 制約 - $ 1\leq\ N,M\ \leq\ 300 $ - $ 1\leq\ A_i,B_i\ \leq\ 10^9 $ - 入力は全て整数 ### Sample Explanation 1 左から順に犬 $ 1 $、猫 $ 2 $、犬 $ 2 $、猫 $ 1 $ と並べたとき、 - 犬 $ 1 $ の不満度は $ 1\times|0-2|=2 $ - 犬 $ 2 $ の不満度は $ 3\times|1-1|=0 $ - 猫 $ 1 $ の不満度は $ 2\times|2-0|=4 $ - 猫 $ 2 $ の不満度は $ 4\times|1-1|=0 $ となるため、不満度の総和は $ 6 $ です。並べ方を変えても不満度の総和が $ 6 $ 未満となることはないため、$ 6 $ が答えです。