Optimal Chocolate Cutting

You are given a rectangular chocolate bar of size \(n \times m\) which is divided into \(n \times m\) pieces. The chocolate has \(n-1\) horizontal cutting lines and \(m-1\) vertical cutting lines. The cost for cutting along the horizontal line \(i\) is given by \(y_i\) and the cost for cutting along the vertical line \(j\) is given by \(x_j\). When you make a cut, it cuts through the entire current piece in that direction. However, note that the cost of a cut must be multiplied by the number of pieces the cut affects in the perpendicular direction.

For example, consider a chocolate bar of size \(4 \times 6\) (i.e. 4 rows and 6 columns). It has 3 horizontal lines with costs \(y_1, y_2, y_3\) and 5 vertical lines with costs \(x_1, x_2, x_3, x_4, x_5\). If you first cut along all horizontal lines, the total cost of horizontal cuts would be \(y_1 + y_2 + y_3\), and then each of the resulting 4 pieces would require vertical cuts with a cost of \(x_1+x_2+x_3+x_4+x_5\) per piece, resulting in an additional cost of \(4 \times (x_1+x_2+x_3+x_4+x_5)\). This might not be optimal. Your task is to determine the minimum total cost to cut the chocolate into individual \(1\times1\) pieces.

Hint: A greedy strategy is optimal. At each step, choose the cut (horizontal or vertical) with the maximum cost remaining. Keep track of the number of segments in the perpendicular direction to multiply the cost accordingly.

inputFormat

The first line contains two integers \(n\) and \(m\) (representing the number of rows and columns, respectively).
The second line contains \(n-1\) space-separated integers: \(y_1, y_2, \ldots, y_{n-1}\), the costs for horizontal cuts.
The third line contains \(m-1\) space-separated integers: \(x_1, x_2, \ldots, x_{m-1}\), the costs for vertical cuts.

outputFormat

Output a single integer, the minimum total cost to cut the chocolate completely into \(1\times1\) pieces.

sample

4 6
2 1 3
4 1 2 3 5

47