题目描述

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

输出

输出结果到标准输出。输出一个整数。

示例输入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