산맥

예제 $1$와 일치하는 두 가지 가능한 높이 배치.

Torunn은 각 칸에 하나의 부지가 있는 $n \times m$ 격자로 이루어진 산악 주거 지역에 산다. Torunn은 격자의 왼쪽 위 모서리 칸에 산다. 안타깝게도 최근 유난히 골치 아픈 세입자가 이사 왔기 때문에, Torunn은 자신의 부동산을 팔고 다른 곳으로 이사하기로 했다. 하지만 먼저 자신의 부동산 가치가 얼마인지 알아내야 한다.

격자의 각 칸에는 높이가 있다. 모든 높이는 서로 다르므로, 편의상 높이가 $1, 2, 3, \dots, n \cdot m$라고 가정하자. 높이가 높은 부지일수록 주택 시장에서 더 가치가 있으므로, Torunn은 자신의 부지 높이를 알아내고 싶어 한다. 따라서 그녀는 격자의 각 칸을 돌아다니며 인접한 칸 중 높이가 더 낮은 칸이 몇 개인지 확인했다. 두 칸이 한 변을 공유하면 인접한 것으로 간주한다(격자 가장자리에 있지 않은 칸에는 인접한 칸이 $4$개 있다).

Torunn이 수집한 정보가 주어질 때, 그녀의 부지가 가질 수 있는 최소 높이와 최대 높이를 구하는 프로그램을 작성하라.

채점

여러 테스트 그룹으로 이루어진 테스트 세트로 제출한 풀이를 평가하며, 각 테스트 그룹에는 정해진 점수가 배정된다. 각 테스트 그룹에는 여러 테스트 케이스가 포함된다. 한 테스트 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 해결해야 한다.

그룹 | 점수 | 제한 조건

$1$ |$20$| $n = 1$

$2$ |$20$| $n = m \leq 3$

$3$ |$20$| $n = m \leq 4$

$4$ |$40$| 추가 제한 조건 없음.

첫째 줄에 격자의 행과 열의 수를 나타내는 두 정수 $n$와 $m$가 주어진다($1 \leq n, m \leq 8$).

이어지는 $n$개의 줄에는 각각 길이가 $m$인 문자열이 주어진다. 이 격자는 Torunn이 수집한 정보를 나타내며, 각 숫자는 그 숫자가 있는 칸보다 높이가 낮은 인접한 칸의 개수를 나타낸다. 수집한 정보가 올바르도록 각 칸에 높이 $1, 2, \dots, n \cdot m$를 배정하는 방법이 적어도 하나 존재함이 보장된다. 수집된 값은 항상 $0$에서 $4$ 사이임에 유의하라.

왼쪽 위 모서리 칸이 가질 수 있는 최소 높이와 최대 높이를 두 정수로 출력한다.