Minimum Cost Connected Cells

An N x M rectangular grid is divided into 1 x 1 cells. Each cell contains one integer, called that cell's cost.

Find a connected set of cells whose total cost is as small as possible. The cost of a set is the sum of the values written in all cells in the set.

A set of cells is connected if, starting from any cell in the set, every other cell in the set can be reached by moving only through cells in the set and only between side-adjacent cells. Two cells are adjacent when they share an edge. The empty set of size 0 is also allowed, and its cost is 0.

The first line contains two positive integers N and M. Both N and M are at most 9.

Each of the next N lines contains M integers, the costs of the cells. The absolute value of each integer is at most 1000.

Print the minimum possible cost of a connected set of cells.