Bow Meow 最优化

题目描述

有 $N$ 只狗,编号为 $1$ 到 $N$,以及 $M$ 只猫,编号为 $1$ 到 $M$。 将这 $(N+M)$ 只动物从左到右排成一排。

每只动物的沮丧程度如下:

• 狗 $i$ 的沮丧程度为 $A_i\times|x-y|$,其中 $x$ 和 $y$ 分别表示该狗左侧和右侧的猫的数量。
• 猫 $i$ 的沮丧程度为 $B_i\times|x-y|$,其中 $x$ 和 $y$ 分别表示该猫左侧和右侧的狗的数量。

求所有动物的沮丧程度之和的最小可能值。

输入格式

输入按以下格式从标准输入给出:

$N$ $M$
$A_1$ $A_2$ $\ldots$ $A_N$
$B_1$ $B_2$ $\ldots$ $B_M$

输出格式

输出答案(一个整数)。

样例

2 2
1 3
2 4

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

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$