Icy Roads Of Nomel
Do you think that driving is easy? This is not the case when the roads are covered with ice.
The city of Nomel has exactly N+1 streets (west-east roads) and M+1 avenues (north-south roads). Each street intersects each avenue, so each street is divided into M blocks and each avenue is divided into N blocks.
It's winter, and each road of the city is covered with a thick ice layer. As driving on ice is a bit tricky, each road has its own time of driving through one block of this road. This value is constant along all blocks of the road.
Obviously, you can drive only through the roads. Now your task is to find a route from the north-western intersection of the city to the south-eastern one with the minimum driving time. This route must also be the shortest one, that is, it should pass through exactly N+M blocks.
Input
The first line contains two integers N and M (1 ≤ N, M ≤ 500 000). The second line contains N+1 positive integers representing the driving times of Nomel streets, given in the order from north to south. The third line contains M+1 positive integers representing the driving times of Nomel avenues, given in the order from west to east. It's guaranteed that none of these numbers exceed 10^9.
Output
Print one integer - the required minimum total driving time.