Charlie wants to divide a big piece of waffle which is made up of m*n square pieces. Each piece is of size 1*1. The shape of waffle is a rectangle of dimension m*n. However, Charlie can break the waffle either horizontally or vertically, along the lines such that the square pieces are not destroyed.
Each break along a line has a certain cost associated with it. The cost is only dependent on the line along which the waffle is being broken, and not on its length.
The total cost is obtained by summing up the costs of all the breaks.
Given the cost associated with each line, Charlie wants to know the minimum cost of breaking the waffle into single square pieces.
First line contains two integers m and n denoting the number of rows and columns respectively.
This is followed by m-1, each line contains an integer denoting the cost of breaking a waffle along a horizontal line.
This is followed by n-1, each line contains an integer denoting the cost of breaking a waffle along a vertical line.
Output should be a single line integer denoting the minimum cost to break the waffle into single square pieces.
Break the waffer along the column where the cost = 4, then break the two pieces along the row where the cost = 3*2 = 6. Otherwise, the cost would have been 3+(4*2) = 11.