Camelot Gathering

A chessboard contains one king and several knights. Find the minimum number of moves needed to gather the king and every knight on one square.

The king may move to any one of the 8 neighboring squares in one move. A knight moves as in chess: 2 squares in one direction and 1 square perpendicular to it.

If the king and at least one knight are on the same square, the king may mount one of those knights. Mounting does not count as a move. After mounting, the king moves together with that knight using knight moves, and the king cannot dismount.

A knight may move to the king's square to pick up the king, the king may move to a knight's square and mount it, or they may meet at some intermediate square where the king mounts the knight.

Given the initial positions of the king and the knights, output the minimum number of moves required to gather them all on a single square.

The first line contains two integers N and M, the size of the chessboard. N is the number of rows and M is the number of columns. 1 <= N <= 40 and 1 <= M <= 26.

The next line contains the king's position as a letter X and an integer Y. X is the column, written as an uppercase letter starting from A. Y is the row number.

After that, knight positions are given in the same format until the end marker -1 -1 appears.

There may be no knights, or the board may be filled with knights. No two knights occupy the same square.

Output the minimum number of moves needed to gather the king and all knights on one square. The gathering square may be any square on the board.

If the king is on D4 and the knights are on A3, A8, H1, and H8, they can gather on B5. The first knight moves A3 -> B5; the second moves A8 -> C7 -> B5; the third moves H1 -> G3 -> F5 -> D4, picks up the king, and then moves to B5; the fourth moves H8 -> F7 -> D6 -> B5.