Peg solitaire

Recently, Hugo became interested in the famous game of Peg solitaire. The game has been known at least since the 17th century and there exist many variants of it. To make it more challenging Hugo decided to give the game a bit more computational flavour and created his own rules.

The rules of Hugo's Peg solitaire:

• The game is played on a rectangular board with M rows and N columns of holes.
• Each hole is assigned a positive cost. The costs of different holes may be different.
• At the beginning of the game each hole can contain at most one peg and at least one hole must be empty.
• The game proceeds in moves. A valid move is to take a peg and jump it over an adjacent peg into an empty hole two positions away and then to remove the jumped peg and also the peg which is three positions away from the original position of the jumping peg, if such peg exists. Therefore, in each move either one or two pegs are removed.
• Jumping is allowed only in the directions along rows and columns (no diagonal jumps are possible) and the second removed peg, if it exists, must lie in the direction of the jump.
• A cost of the move is the value associated with the hole in which the jumping peg lands.
• The game ends when there is no valid move.
• The cost of the game is the sum of costs of all its moves.
• The objective of the game is to minimize the cost of the game.

     

Image 1. Example of Peg solitaire game played according to the Hugo's rules. The leftmost scheme shows the initial position of the game. Note that the cost of the game, which is 8, is not minimal.

The task

You are given the diagram of the game board describing the costs of the holes and the initial positions of the pegs. The task is to find a sequence of moves which minimizes the cost of the game played by the Hugo's rules.

---

Input

The input describes the initial position on the game board and contains some text lines. Each line specifies one row of the board. The line contains several strings separated by at least one space, each string specifies one hole. The hole specification is an integer equal to the cost of the hole. If, and only if, there is a peg in the hole in the initial position then the cost is immediately preceded by the hash sign '#'. There is no space between the hash sigh and the cost of the hole. The number of the strings on each line is equal to the number of columns on the board, the number of input lines is equal to the number of rows on the board. The order of input lines and strings on lines reflects the order of rows and columns on the board.
For the number of rows M and the number of columns N holds 1 ≤ M, N ≤ 10, 6 ≤ M × N ≤ 30.
The costs of holes are integers from the interval <1, 1000 >.

Output

Output contains two text lines. The first line contains the minimum possible cost of the game which initial position is specified by input data. The second line contains list of moves leading to the minimum cost of the game. Each move is described by a pair of coordinates of the original and the landing position of the peg which is being jumped in that move. The coordinates of a hole are enclosed in square brackets and separated by comma and contain no spaces. First is the row coordinate, next is the column coordinate. The rows are indexed from 0 to M−1 starting with the top row, the columns are indexed from 0 to N−1 starting with leftmost column. The pair of coordinates is connected with the string "->" (minus sign followed by the "greater than" sign). Individual pairs of coordinates are separated by two spaces. When there is more than one sequence of moves which leads to the same minimum cost of the game then the output list of moves, interpreted as a string, must be lexicographically smallest possible.

Example 1

Input

  4 #5 #4  2  1
  4 #5  1 #4  1
 #6  5 #4 #5  4
  2 #6 #1  3  2

The input of the Example 1 specifies the initial position of the game depicted in the Image 1 above. Note that the minimum value of the game and the corresponding sequence of moves differs from that in the Image 1.

Output

4
[0,1]->[0,3]  [3,2]->[1,2]  [1,2]->[1,4]

Example 2

Input

  #5  19  17 #17 #17   7
 #19 #14  #3  16 #19   7
  #5 #19  #6 #17 #14  #2
  #8  11  #7  #7 #10  #6
   2 #10 #16  14 #16  #8

Output

50
[2,0]->[4,0]  [2,2]->[2,0]  [1,0]->[3,0]  [3,5]->[1,5]  [2,3]->[2,5]  [0,4]->[2,4]  [1,5]->[3,5]  [4,2]->[2,2]  

Example 3

Input

179 #145 #195  157 #138 #120 #156 #199  151  117

Output

277
[0,5]->[0,3]  [0,7]->[0,5]

Example 4

Input

  5 #5 #5 #5 #5  5
 #5 #5 #5 #5 #5 #5
 #5 #5 #5 #5 #5 #5
  5 #5 #5 #5 #5  5

Output

35
[0,2]->[0,0]  [0,3]->[0,5]  [1,0]->[3,0]  [1,5]->[3,5]  [2,2]->[0,2]  [1,4]->[1,2]  [2,4]->[2,2]

---

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set