최소 비용 연결 칸

N x M 크기의 직사각형 격자가 1 x 1 칸으로 나누어져 있다. 각 칸에는 정수 하나가 적혀 있으며, 이 값을 그 칸의 비용이라고 한다.

연결된 칸들의 집합 중 비용의 합이 가장 작은 것을 찾아라. 집합의 비용은 포함된 모든 칸에 적힌 비용의 합이다.

칸들의 집합이 연결되어 있다는 것은, 집합 안의 임의의 한 칸에서 다른 칸으로 이동할 때 집합에 포함된 칸들만 지나며 상하좌우로 인접한 칸을 통해 갈 수 있다는 뜻이다. 두 칸은 변을 공유할 때 인접하다. 아무 칸도 고르지 않은 크기 0의 집합도 허용되며, 그 비용은 0이다.

첫째 줄에 자연수 N과 M이 주어진다. N과 M은 9보다 작거나 같다.

둘째 줄부터 N개의 줄에 각 칸의 비용을 나타내는 정수 M개가 주어진다. 각 정수의 절댓값은 1000보다 작거나 같다.

가능한 연결된 칸 집합의 비용 중 최솟값을 출력한다.