Cutting the Wooden Board

Given an \(N \times M\) wooden board, you are required to cut it into \(1 \times 1\) squares. The board can only be cut along the grid lines, and each cut along a specific horizontal or vertical line has an associated cost, which may vary.

When a board is cut, it splits into two smaller pieces. You cannot join separate pieces and then make a single cut; instead, each piece must be cut individually. Thus, every cut decision is made on one board at a time.

You are given the costs for cutting along each available line. For a board of size \(N \times M\), there are \(N-1\) horizontal cut costs and \(M-1\) vertical cut costs. Determine the minimum total cost required to cut the entire board into \(1 \times 1\) squares.

Input/Output Note: All formulas are written in \(\LaTeX\) format.

inputFormat

The first line contains two integers \(N\) and \(M\) (\(2 \leq N, M \leq 10^4\)), representing the dimensions of the board in terms of unit squares.

The second line contains \(N-1\) integers, representing the cost to make each horizontal cut.

The third line contains \(M-1\) integers, representing the cost to make each vertical cut.

outputFormat

Output a single integer representing the minimum total cost to cut the board into \(1 \times 1\) squares.

sample

2 2
2
1

4