Description

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.

Input Format

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 Format

Output a single integer, the minimum total cost.

2 2
3
3

9

Hint

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