얼마 전 대통령 선거를 한 월드나라는 선거 조작 의혹으로 12개의 소국가로 나누어졌다.

제1국. Noisulagem, 최백준에 의해 세워진 국가로 월드를 전혀 계승하고 있지 않다.

제2국. WonderGirls, 소희의 남자친구인 신동혁에 의해 세워진 국가다. 5명의 여왕과 1명의 왕이 존재하는 왕족국가이다.

제3국. SoSiNine, 양항승이 소녀시대 9명을 모두 납치해서 만든, 양항승 국왕에 의해 통치되는 국가이다. 효연을 제외한 나머지 멤버는 지하감옥에 갇혀 죽음만 기다리는 삶을 살고 있고, 효연은 양항승의 부인으로 살고 있다.

제4국. ODuck^2, 오직 오타쿠를 위한 국가이다. 이 나라의 비자를 받으려면 미연시 오타쿠 테스트와 일본애니 테스트에서 모두 만점을 받아야 한다. 사용하는 언어는 일본어이다. おたく ふぃえちん。

제5국. SocWorld, 월드에서 위닝을 하던 사람들이 만든 국가로, 해외 축구리그를 좋아한다. 현재 축구리그의 활성화방안이 국가 제1정책이며, 해외 리그의 여러 선수를 막강한 오세준의 자금으로 사들이려고 한다. 위닝 개발자가 이 나라에 납치되어 있다.

제6국. AntiSJ, 오세준을 라이벌로 생각하는 성혁화가 세운 국가이다. 가위바위보를 할 때 이기지도 않았으면서 먼저 좋아하고 보는 사람만이 비자를 받을 수 있다.

제7국. 허경영공화국, 허경영이 암살당한 직후 그 뒤를 이은 오민식이 세운 국가이다. 현재 허경영을 국가 원수로 하는 북한식 국가이고, 새마을 운동을 매일 아침 해야 한다. 결혼을 하면 1억 원을 주고, 아이를 낳으면 5천만 원을 주는 등 돈을 뿌리는 국가로, 현재 인플레이션이 진행중이며, 화장실에서 돈을 휴지 대신 쓰고 있다.

제8국. 김치국, 오직 김치만 먹는 나라. 설명이 필요 없다.

제9국. HHComeOn, 이정문에 의해 세워진 국가로 힙합이 난무한다.

제10국. FTZ, 판타지 소설을 매일 읽어야 한다. 학교에서 판타지 소설을 읽지 않으면 맞는다. 수능시험에서 박종현이 만족할 만한 판타지 소설을 써야 판타지 대학교에 입학할 수 있다.

제11국. EZ2DJ, 오직 건반게임만을 할 수 있다. 스타를 하면 사형. 악덕 국왕 임현수에 의해 많은 사람들이 죽고 있다. 매일 밤 자신과 EZ2DJ를 대결할 사람을 구한 뒤, 자신보다 잘하지 못하면 그 자리에서 처형하는 나라로 유명하다. 매일 1명씩 사라지기 때문에 다른 나라에서 납치를 해 온다.

제12국. 테디, 듣보잡.

서로 독자적으로 잘 살고 있던 월드는 오영식의 침략을 받게 되었다. 오영식은 월드를 점령할 목적으로 레이스, 배틀크루저, 발키리, 사이언스 베슬, 마린, 파이어뱃, 고스트, 메딕, SCV를 포함한 130부대를 데리고 오기 시작했다.

여러 국가의 상위 지도계층들은 서로 긴급 회의를 하려고 한다. 월드는 체스판처럼 이루어져 있다. 지도계층들은 교통수단인 마알을 타고 간다. 마알은 1-마알부터 9-마알 까지 있다. 1-마알은 체스판의 나이트처럼 움직일 수 있으며, K-마알은 한 번에 나이트처럼 K번까지 연속으로 움직일 수 있다.

체스판의 모습과 각각의 K-마알의 위치가 주어졌을 때, 서로 한 곳에 모일 수 있는 최소 이동 횟수를 구하는 프로그램을 작성하시오.

첫째 줄에 체스판의 세로 크기 N, 가로 크기 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 체스판의 정보가 주어진다. 체스판은 .과 1-9 숫자로만 이루어져있다. "."은 빈 칸이고, 숫자 K는 해당 위치에 K-마알이 놓여 있음을 의미한다.

모든 마알의 이동 횟수의 합의 최솟값을 출력한다. 한 곳에 모일 수 없다면, -1을 출력한다.