P3173 [HAOI2009] Chocolate

There is a rectangular chocolate bar of size $n \times m$, to be cut into $n \times m$ pieces. There are $n-1$ horizontal lines and $m-1$ vertical lines on the bar. Each time, you may cut along one of these horizontal or vertical lines. Regardless of the cut length, the costs of cutting along the horizontal lines in order are $y_1,y_2,\cdots,y_{n-1}$, and along the vertical lines in order are $x_1,x_2,\cdots,x_{m-1}$. For the $6 \times 4$ chocolate shown below, suppose we first cut along the three horizontal lines, requiring $3$ cuts, producing $4$ chocolate strips. Then we cut these $4$ strips along the vertical lines, each requiring $5$ cuts. The total cost is $y_1+y_2+y_3+4 \times (x_1+x_2+x_3+x_4+x_5)$.  Of course, the simple method above is not necessarily optimal. How should we cut this chocolate bar to minimize the total cost?

The first line contains two integers $n$ and $m$. The next $n-1$ lines each contain one integer, representing $y_1,y_2,\cdots,y_{n-1}$. The next $m-1$ lines each contain one integer, representing $x_1,x_2,\cdots,x_{m-1}$.

Output a single integer, the minimum cost to cut the chocolate.

For $30\%$ of the testdata, $n \leq 100,m \leq 100$. For $100\%$ of the testdata, $n \leq 10000,m \leq 10000$. Translated by ChatGPT 5