当前没有测试数据。

Ex - Bow Meow Optimization

分数：600分

问题描述

有$N$只狗编号为$1$到$N$，$M$只猫编号为$1$到$M$。你需要将这$(N+M)$只动物从左到右排列在一条直线上。每种排列方式都会引起每只动物的沮丧程度，具体规则如下：

• 第$i$只狗的沮丧程度为$A_i \times |x-y|$，其中$x$和$y$分别代表该狗左边和右边的猫的编号。
• 第$i$只猫的沮丧程度为$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$

输出

输出一个整数作为答案。

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