Cost of the route#4444
On each square of an 8 \times 8 chessboard, a non-negative integer is written. The king can move from the bottom-left corner to the top-right corner of the board, with allowed moves being right, up, or diagonally right-up. The cost of moving through a square is determined by the number written on it.
Your task is to guide the king from the bottom-left corner to the top-right corner with the minimum possible passage cost.
The input consists of eight rows, each containing eight non-negative integers, none of which exceed . The number is always located in the bottom-left corner.
Output a single number on the first line, representing the minimum cost to travel from the bottom-left corner to the top-right corner. On the second line, output the sequence of squares that the king travels through, separated by a single space. The path should begin at square a1 and conclude at square h8.
Example 1