시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 91 6 4 23.529%

문제

1*1크기의 정사각형으로 나누어진 N*M크기의 직사각형 종이가 있다. 각 칸에는 정수가 하나씩 쓰여져 있다. 이 숫자를 비용이라고 하자.

이 때, 가장 싼 연결된 칸의 집합을 찾는 프로그램을 작성하시오. 연결된 칸의 집합의 비용은 각 칸에 써 있는 비용의 합이다.

칸이 연결되어 있다는 말은 그 집합의 한 칸에서 다른 칸으로 집합에 포함된 인접한 칸을 통해서 모두 이동할 수 있다는 의미이고, 두 칸이 인접해 있다는 소리는, 같은 변을 공유할 때이다.
 

입력

첫째 줄에 N과 M이 주어진다. N과 M은 9보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 숫자가 M개씩 주어진다. 각 숫자는 절댓값이 1000보다 작거나 같은 정수이다.

출력

첫째 줄에 가장 싼 연결된 칸의 집합의 비용을 출력한다.

예제 입력

2 2
-10 1
2 -10

예제 출력

-19

힌트

출처