- Prepare
- Algorithms
- Graph Theory
- Travelling Salesman in a Grid

# Travelling Salesman in a Grid

# 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**

```
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