Maal Gathering

Interview

Time limit2sMemory limit128 MB

Summary

Given a grid with K-Maal pieces that jump up to K knight moves per turn, find the minimum total moves to gather all pieces on one square.

Level: Medium5 of 10
Topics: BFS, Shortest path, Brute force, Matrix
Solved: No attempts yet

Problem

A Maal is a piece that moves on a chessboard. The board may contain 1-Maals, 2-Maals, ..., and 9-Maals.

A K-Maal can make up to K consecutive knight moves as one move. You want to gather every Maal on the board onto a single square. Only one Maal can be moved at a time, and multiple Maals may occupy the same square during or after movement.

Find the minimum number of moves needed to gather all Maals on one square.

Input

The first line contains the board height N and width M. The next N lines describe the board from top to bottom. Each row is given as a length-M string with no spaces.

An empty square is written as .. A digit K means that a K-Maal is placed on that square. The input contains at least one Maal.

Output

Print the minimum number of moves required to gather all Maals on one square. If it is impossible to gather them on one square, print -1.

Constraints

1 ≤ N, M ≤ 10
Each Maal's K is an integer from 1 to 9.

Examples5

Example 1
Input
```
3 4
...1
....
2...
```
Expected output
```
2
```

Example 2

Input

8 8
........
.1......
........
....3...
........
........
.7......
........

Expected output

Example 3
Input
```
3 2
..
2.
..
```
Expected output
```
0
```
Example 4
Input
```
1 8
.1....1.
```
Expected output
```
-1
```

Example 5

Input

Expected output