Optimal Chocolate Cutting

You are given a rectangular chocolate bar of size \(n \times m\). The chocolate is divided by \(n-1\) horizontal lines and \(m-1\) vertical lines, so that it can be eventually split into \(n \times m\) unit pieces.

Cutting the chocolate is done by making straight cuts along one of these lines. Each horizontal cut (cutting along a horizontal line) has an associated cost; the costs are given by \(y_1, y_2, \dots, y_{n-1}\). Similarly, each vertical cut (cutting along a vertical line) has an associated cost given by \(x_1, x_2, \dots, x_{m-1}\).

When you perform a cut, it affects all the current pieces that the cut line goes through. For example, one simple (but not necessarily optimal) way would be:

• Cut along some horizontal lines first. Suppose you make \(k\) horizontal cuts. Then the bar will be divided into \(k+1\) horizontal segments.
• After that, every vertical cut will be applied to all the horizontal pieces.

If you first cut along three horizontal lines, and then cut vertically across all pieces, the total cost is:

[ \text{Total Cost} = y_1 + y_2 + y_3 + (k+1)\times (x_1+x_2+\cdots+x_{m-1}). ]

Your goal is to determine the minimum total cost required to cut the \(n \times m\) chocolate into \(n \times m\) single pieces. An optimal strategy is to choose the order of cuts greedily: at each step, make the cut (horizontal or vertical) that has the highest cost available, and then update the number of segments accordingly.

The greedy strategy is as follows:

1. Sort the horizontal costs \(y_i\) in descending order and similarly, sort the vertical costs \(x_j\) in descending order.
2. Initialize the number of current horizontal segments as 1 and vertical segments as 1.
3. While there are unperformed cuts in both arrays, choose the cut with the greater cost. If a horizontal cut is chosen, add its cost multiplied by the current number of vertical segments, and increase the number of horizontal segments by 1. Otherwise, if a vertical cut is chosen, add its cost multiplied by the current number of horizontal segments, and increase the number of vertical segments by 1.
4. If one of the arrays is exhausted, process all remaining cuts from the other array accordingly.

Compute and output the minimum total cost.

inputFormat

The input consists of three lines:

1. The first line contains two integers \(n\) and \(m\) \( (2 \le n, m \le 10^5)\), representing the dimensions of the chocolate.
2. The second line contains \(n-1\) integers \(y_1, y_2, \dots, y_{n-1}\) representing the costs for horizontal cuts.
3. The third line contains \(m-1\) integers \(x_1, x_2, \dots, x_{m-1}\) representing the costs for vertical cuts.

outputFormat

Output a single integer, the minimum total cost to break the chocolate into \(n \times m\) pieces.

sample

2 2
2
1

4