[Poi2003]Chocolate

有一块 $n\times m$ 的矩形巧克力，准备将它切成 $n\times m$ 块。巧克力上共有 $n-1$ 条横线和 $m-1$ 条竖线，你每次可以沿着其中的一条横线或竖线将巧克力切开，无论切割的长短，沿着每条横线切一次的代价依次为 $y_1, y_2, \dots, y_{n-1}$，而沿竖线切割的代价依次为 $x_1, x_2, \dots, x_{m-1}$。

例如对于一块 $6\times 4$ 的巧克力，我们先沿着三条横线切割，需要 $3$ 刀，得到 $4$ 条巧克力，然后再把这 $4$ 条巧克力沿竖线切割，每条都需要 $5$ 刀，则最终所花费的代价为

$$y_1+y_2+y_3+4\times(x_1+x_2+x_3+x_4+x_5).$$

当然，上述简单切法不见得是最优切法。那么怎样切割该块巧克力，花费的代价最少呢？

输入格式

第一行为两个整数 $n$ 和 $m$。

接下来 $n-1$ 行，每行一个整数，分别代表 $x_1, x_2, \dots, x_{n-1}$。

接下来 $m-1$ 行，每行一个整数，分别代表 $y_1, y_2, \dots, y_{m-1}$。

输出格式

输出一个整数，为切割巧克力的最小代价。

样例输入

6 4
2
1
3
1
4
4
1
2

样例输出

42

数据范围

• 对于 $30\%$ 的数据，$n\le 100$，$m\le 100$；
• 对于 $100\%$ 的数据，$n\le 10^4$，$m\le 10^4$。

来源与许可

本题为 POI 2003 试题「Chocolate」，题面与测试数据整理自 BZOJ 2430。

样例 1

输入

6 4
2
1
3
1
4
4
1
2

输出

42