Maal Gathering

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.

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.

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.

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