The travelling salesman has a map containing m*n squares. He starts from the top left corner and visits every cell exactly once and returns to his initial position (top left). The time taken for the salesman to move from a square to its neighbor might not be the same. Two squares are considered adjacent if they share a common edge and the time taken to reach square b from square a and vice-versa are the same. Can you figure out the shortest time in which the salesman can visit every cell and get back to his initial position?
Input Format
The first line of the input is 2 integers m and n separated by a single space. m and n are the number of rows and columns of the map.
Then m lines follow, each of which contains (n – 1) space separated integers. The jth integer of the ith line is the travel time from position (i,j) to (i,j+1) (index starts from 1.)
Then (m-1) lines follow, each of which contains n space integers. The jth integer of the ith line is the travel time from position (i,j) to (i + 1, j).
Constraints
1 ≤ m, n ≤ 10
Times are non-negative integers no larger than 10000.
Output Format
Just an integer contains the minimal time to complete his task. Print 0 if its not possible to visit each cell exactly once.
Sample Input
2 2
5
8
6 7
Sample Output
26
Explanation
As its a 2*2 square, all cells are visited. 5 + 7 + 8 + 6 = 26