/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
1 から N までの番号がついた N 匹の犬と、1 から M までの番号がついた M 匹の猫がいます。 今から、これらの N+M 匹を左右一列に好きな順序で並べます。 並べ方に応じて、それぞれの犬と猫には以下のように不満度が生じます。
- 犬 i の不満度は、その犬より左にいる猫の匹数を x、右にいる猫の匹数を y とすると、A_i\times|x-y| である。
- 猫 i の不満度は、その猫より左にいる犬の匹数を x、右にいる犬の匹数を y とすると、B_i\times|x-y| である。
不満度の総和の最小値を求めてください。
制約
- 1\leq N,M \leq 300
- 1\leq A_i,B_i \leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 \ldots A_N B_1 B_2 \ldots B_M
出力
答えを整数として出力せよ。
入力例 1
2 2 1 3 2 4
出力例 1
6
左から順に犬 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 が答えです。
入力例 2
1 2 100 100 290
出力例 2
390
入力例 3
5 7 522 575 426 445 772 81 447 629 497 202 775 325
出力例 3
13354
Score : 600 points
Problem Statement
There are N dogs numbered 1 through N and M cats numbered 1 through M. You will arrange the (N+M) animals in a line from left to right. An arrangement causes each animal's frustration as follows:
- The frustration of dog i is A_i\times|x-y|, where x and y are the numbers of cats to the left and right of that dog, respectively.
- The frustration of cat i is B_i\times|x-y|, where x and y are the numbers of dogs to the left and right of that cat, respectively.
Find the minimum possible sum of the frustrations.
Constraints
- 1\leq N,M \leq 300
- 1\leq A_i,B_i \leq 10^9
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 A_2 \ldots A_N B_1 B_2 \ldots B_M
Output
Print the answer as an integer.
Sample Input 1
2 2 1 3 2 4
Sample Output 1
6
Consider the following arrangement: dog 1, cat 2, dog 2, cat 1, from left to right. Then,
- dog 1's frustration is 1\times|0-2|=2;
- dog 2's frustration is 3\times|1-1|=0;
- cat 1's frustration is 2\times|2-0|=4; and
- cat 2's frustration is 4\times|1-1|=0,
so the sum of the frustrations is 6. Rearranging the animals does not make the sum less than 6, so the answer is 6.
Sample Input 2
1 2 100 100 290
Sample Output 2
390
Sample Input 3
5 7 522 575 426 445 772 81 447 629 497 202 775 325
Sample Output 3
13354