마알 모으기

마알은 체스판 위에서 움직이는 말이다. 체스판에는 1-마알, 2-마알, ..., 9-마알이 놓일 수 있다.

K-마알은 한 번의 이동에서 나이트의 이동을 최대 K번 연속으로 할 수 있다. 체스판 위의 모든 마알을 하나의 칸에 모으려고 한다. 한 번에는 마알 하나만 움직일 수 있으며, 이동 중이거나 이동이 끝난 뒤 같은 칸에 여러 마알이 있어도 된다.

모든 마알을 한 칸에 모으는 데 필요한 이동 횟수의 최솟값을 구하라.

첫째 줄에 체스판의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 체스판의 상태가 위쪽 행부터 순서대로 주어진다. 각 행은 공백 없이 길이 M의 문자열로 주어진다.

빈 칸은 .으로 표시된다. 숫자 K는 그 칸에 K-마알이 놓여 있음을 뜻한다. 입력에는 하나 이상의 마알이 포함된다.

모든 마알을 하나의 칸에 모으기 위해 필요한 이동 횟수의 최솟값을 출력한다. 모든 마알을 한 칸에 모을 수 없다면 -1을 출력한다.

• 1 ≤ N, M ≤ 10
• 각 마알의 K는 1 이상 9 이하의 정수이다.