Birthday Cake

It is your friend's birthday and you have decided to bake them a cake. However, this is your first time baking anything and you turn out to not be very good at it. Due to your naïve overconfidence, you decided not to follow any recipe nor to measure any of the ingredients. As a result, you actually have no idea how much cake you have made, or whether there will be enough for all of the guests at your friend's party. On top of being incompetent, you also happen to be an extremely slow baker, and are already running late for your friend's party, and thus don't have the time to accurately measure the volume of cake you have produced. This is exacerbated by the fact that instead of having a nice rectangular shape with uniform thickness, your creation is an uneven mess. The only way to calculate its exact volume would be to measure its depth at every point, something which you do not have the time to do.

Instead, you decide to divide your cake into $N$ rows and $M$ columns, each a centimetre wide, thus dividing the cake into $N \times M$ square centimetre cells. Then, you record the thickness in centimetres of the thickest cell in each row and column (you may assume that within each cell thickness is uniform, and that each cell has a non-zero, integer thickness). You then use these measurements to calculate the lower and upper bounds for the volume in cubic centimetres of cake you possess. However, since you are running so low on time, you must write a program to do this calculation for you.

Input

The first line of input contains two space-separated integers: $N$ and $M$, the number of rows and columns in your cake, respectively.

The next line contains $N$ space-separated integers: the maximum thickness of the cells in each of the $N$ rows.

The next line contains $M$ space-separated integers: the maximum thickness of the cells in each of the $M$ columns.

Output

On one line output two space-separated integers: the first should be the minimum volume of cake you can have consistent with your measurements, and the second should be the maximum volume.

Constraints

• $1 \leq N, M \leq 200,000$
• All thickness values are between $1$ and $10^6$ inclusive
• It is guaranteed that there exists at least one cake consistent with the measurements taken

Subtasks

• Subtask 1 (+16%): All rows and all columns have the same maximum thickness.
• Subtask 2 (+18%): $N = M = 2$
• Subtask 3 (+26%): $N, M \leq 2,000$
• Subtask 4 (+40%): No further constraints

Scoring

For each test case you score 0% if your output doesn't follow the specified format, or both integers are wrong. If only one of them is correct, you score 50%. If both are correct, you score 100%. Your score for a subtask is the minimum score across all test cases of that subtask.

Note that even if you are only aiming for 50% on a subtask, you still need to output two integers for the output format to be correct.

Notes

If you are using Python and your solution is exceeding the time limit, try selecting Python 3.11 (PyPy 7.3.19) when submitting as this will generally make your code run faster.

If you are using a type sensitive language like C++, Java, or C then make sure to use a 64-bit integer type to avoid integer overflow. 64-bit integer types include long long for C or C++, and long for C# or Java.

Sample Explanations

Sample 1

Two cakes satisfying the measurements given in sample input 1 with minimum and maximum volumes are shown below.