Kyoto Sightseeing: Minimum Travel Time

In Kyoto, a world‐class sightseeing spot, the streets are laid out in a grid. There are \(H\) east-west streets and \(W\) north-south streets; the intersections are denoted by \((i,j)\) where \(i\) is the street number from the north and \(j\) is the street number from the west. Your starting point is \((1,1)\) and your destination is \((H,W)\). You can only walk east (to the right) or south (downwards) so that you do not take a detour.

The walking speeds on the streets differ. For each east-west street, walking one unit to the right (from \((i,c)\) to \((i,c+1)\) for \(c\in[1,W-1]\)) takes \(A_i\) seconds. Similarly, on each north-south street, walking one unit down (from \((c,j)\) to \((c+1,j)\) for \(c\in[1,H-1]\)) takes \(B_j\) seconds.

Your task is to compute the minimum time required to travel from \((1,1)\) to \((H,W)\) under these conditions.

Note: The input guarantees the optimal path uses exactly \(H-1\) moves down and \(W-1\) moves to the right.

inputFormat

The first line contains two integers \(H\) and \(W\) representing the number of east-west and north-south streets respectively.

The second line contains \(H\) integers \(A_1, A_2, \ldots, A_H\), where \(A_i\) is the time (in seconds) needed to walk one unit distance east on the \(i\)th east-west street.

The third line contains \(W\) integers \(B_1, B_2, \ldots, B_W\), where \(B_j\) is the time (in seconds) needed to walk one unit distance south on the \(j\)th north-south street.

outputFormat

Output a single integer representing the minimum time (in seconds) needed to travel from \((1,1)\) to \((H,W)\).

sample

3 3
3 2 1
2 3 4

6