分数: 600 点
问题陈述
有 N 狗编号 1 通过 N 和 M 猫编号 1 通过 M。 您将安排 (N+M) 动物从左到右排成一排。 一种安排导致每只动物 挫败感 如下:
- 狗的挫败感 i is A_i\times|x-y|,其中 x 和 y 分别是该狗左边和右边猫的数量。
- 猫的挫败感 i is B_i\times|x-y|,其中 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