题目描述

$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$

输出格式

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

题目大意

$n$ 只狗和 $m$ 支猫（编号从 $1$ 开始）排成一列，第 $i$ 只狗权值为 $a_i$，第 $i$ 只猫权值为 $b_i$。

对于一种排列方案，设第 $i$ 只狗左侧、右侧猫数目分别为 $l_i$、$r_i$，第 $i$ 只猫左侧、右侧狗数目分别为 $p_i$、$q_i$，定义此排列的不和谐度为 $(\sum_{i=1}^na_i|l_i-r_i|)+(\sum_{i=1}^mb_i|p_i-q_i|)$。

求所有排列方案中不和谐度的最小值。

2 2
1 3
2 4

6

1 2
100
100 290

390

5 7
522 575 426 445 772
81 447 629 497 202 775 325

13354

提示

制約

• $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$ が答えです。