Eight Puzzle

[CENStudent]

In 8-Puzzle game, you are given a square frame puzzle which consists of 8 numbered tiles and one missing tile. By shifting the tiles to the empty tile position, you are asked to put the numbers in proper order. Your professor is developing a program to solve this problem automatically. For this, he wants to compare and calculate the distance of puzzles. If two numbers are in the same x,y coordinates then the distance is zero. If two numbers are in different coordinates, manhattan distance of two numbers is calculated.

Question: Write a program that reads n matrix configuration and then it finds the configuration with the closest distance.

Input specification
You will be given two integers (n and k) where 0 ≤ n ≤ 500 and 1 ≤ k ≤ 10. Then, in the following n lines you will be given k2 integers where each number is between 0 and k2 and zero (0) represents the position of the empty tile.

Output specification
Show two numbers: Minimum distance and the row of it. Note: If there are several minimum results then show the first appearance.


Sample Input I
3 3
7 3 5 4 0 2 1 8 6
1 5 0 4 2 8 7 6 3
8 1 3 2 5 4 6 7 0
Sample Input II
3 4
4 13 14 2 10 8 5 3 6 1 12 9 11 15 7 0
8 12 10 3 4 7 2 14 9 6 15 5 0 13 1 11
1 3 15 5 14 2 10 12 0 7 9 8 11 6 4 13
Sample Output I
8 2
Sample Output II
32 3

URL http://acm.epoka.edu.al:8080/en/problem-pid-c511?ps=1&smt=a&smpwid=0