P1324 Rectangle Partition

For certain needs, we need to cut an $N \times M$ wooden board into $1 \times 1$ small squares. For a board, we may only cut along a horizontal or a vertical grid line (on the grid lines). The board is non-uniform, so cutting along different lines costs different amounts. Each cut splits one current piece into two pieces. You cannot put pieces together and make a single cut across them to get four pieces; you must cut the two pieces separately. Given the costs of cutting along each line, find the minimum total cost to partition the whole board into $1 \times 1$ squares.

The first line contains $N$ and $M$, denoting an $N \times M$ board. The second line contains $N - 1$ non-negative integers, representing the costs of cutting along the $N - 1$ horizontal grid lines. The third line contains $M - 1$ non-negative integers, representing the costs of cutting along the $M - 1$ vertical grid lines.

Output a single integer, the minimum total cost.

Constraints: - For $60\%$ of the testdata, $1 \le N, M \le 100$. - For $100\%$ of the testdata, $1 \le N, M \le 2000$. Translated by ChatGPT 5