Chessboard Gathering

Long ago, King Arthur and his knights celebrated their friendship on New Year’s Day. In memory of these events, we view their stories as a chessboard game. On an 8×8 chessboard (or any board with sufficiently many squares), one king and several knights are placed on different squares (no two knights share the same square). In the game, any square may hold more than one piece without interfering with the pieces’ movement.

The king can move one step to any adjacent square (horizontally, vertically, or diagonally) as long as he does not leave the board. A knight moves in an L‐shape: two squares in one direction and one square perpendicular; again the knight may not leave the board.

The task is to move all the pieces so that they gather on one square using the minimum total number of moves. All pieces (the king and all knights) must move according to their own rules. In addition, you are allowed to choose one knight to meet the king at some intermediate square, and from that meeting point the knight and king move together as a single knight (i.e. using knight moves) – and in such a joint move, the two pieces count as one with respect to move‐count. The other knights move by themselves using knight moves all the way to the gathering square.

You must determine the gathering square and compute the minimal number of moves required so that all pieces are together.

Movement Details:

• King moves: from \( (x,y) \) to any square \( (x',y') \) with \( |x-x'|\le1 \) and \( |y-y'|\le1 \), provided the destination is on the board.
• Knight moves: from \( (x,y) \) to any square \( (x',y') \) satisfying \( (|x-x'|,|y-y'|)=(1,2) \) or \( (2,1) \), provided the destination is on the board.

Merging rule: You may choose one knight to merge with the king. In doing so, the king moves by his rule to a meeting square \( m \) and the chosen knight moves (by knight moves) to \( m \). Then, from \( m \) to the final gathering square \( g \) they move together using knight moves, counting as a single piece. The cost for this merged movement is the sum of:

[ \text{cost}{merge} = d{king}(K, m) + d_{knight}(n, m) + d_{knight}(m, g), ]

while if the pieces were to move independently the cost would have been:

[ \text{cost}{indep} = d{king}(K, g) + d_{knight}(n, g). ]

Your goal is to find the minimum total moves considering all knights and the possibility of merging exactly one knight with the king.

inputFormat

The input consists of a single line containing the positions of the pieces on the board. The first token is the king’s position, followed by one or more tokens representing the positions of the knights. Each position is given in standard chess notation (a letter from A to H specifying the column, followed by a digit from 1 to 8 specifying the row). Tokens are separated by spaces.

For example:

D4 A3 A8 H1 H8

outputFormat

Output a single integer: the minimum number of moves required to gather all the pieces on one square.

sample

D4 A1

5