P3173 [HAOI2009] 巧克力

有一块 $n \times m$ 的矩形巧克力，准备将它切成 $n \times m$ 块。巧克力上共有 $n-1$ 条横线和 $m-1$ 条竖线，你每次可以沿着其中的一条横线或竖线将巧克力切开，无论切割的长短，沿着每条横线切一次的代价依次为 $y_1,y_2,\cdots,y_{n-1}$，而沿竖线切割的代价依次为 $x_1,x_2,\cdots,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)$。  当然，上述简单切法不见得是最优切法，那么怎样切割该块巧克力，花费的代价最少呢？

无

无

$30\%$ 的数据，$n \leq 100,m \leq 100$； $100\%$ 的数据，$n \leq 10000,m \leq 10000$；