Travelling Salesman in a Grid

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 j^th integer of the i^th 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 j^th integer of the i^th 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

Sample Output

Explanation

As its a 2*2 square, all cells are visited. 5 + 7 + 8 + 6 = 26