최소 비용 영역

문제

$N \times M$ 크기의 격자가 주어진다. 각 칸에는 정수 비용이 적혀 있다.

격자에서 상하좌우로 인접한 칸들로 이루어진 연결된 영역을 하나 선택해야 한다. 이때 아무 칸도 선택하지 않은 빈 영역도 가능하며, 빈 영역의 비용 합은 0이다. 비용 합이 최소가 되는 연결 영역의 비용 합을 구하라.

입력

첫째 줄에 격자의 행의 개수 $N$과 열의 개수 $M$이 공백으로 구분되어 주어진다.
둘째 줄부터 $N$개의 줄에 걸쳐 각 줄마다 $M$개의 정수가 공백으로 구분되어 주어진다. $i+1$번째 줄의 $j$번째 정수는 격자의 $i$행 $j$열에 적힌 비용을 의미한다.

출력

가장 비용이 적은 연결 영역의 비용 합을 출력하라.

제한

• $1 \le N, M \le 9$
• 격자에 주어지는 각 정수의 절댓값은 1,000 이하이다.

입출력 예시

입력 1

2 2
-10 1
2 -10

출력 1

-19

입력 2

3 3
1 2 3
4 5 6
7 8 9

출력 2

0

입력 3

2 3
-5 100 -5
-5 100 -5

출력 3

-10