← 返回题目列表

AtCoder · abc290_h

Ex. 弓喵优化

中文机器翻译题面 查看原题

分数: 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