说明

本题需要使用文件重定向，输入文件名为jump.in,输出文件名为jump.out

题目描述

小美在路上看到一些小学生在玩跳方格，她也想跟着一起玩。

这个方格被划分为 $n \times n$ 的小方格，即有 $n$ 行 $n$ 列。每一个小方格上面都是一个 $1\sim k$ 的正整数。小美想依次从 1,2,…,k 这个顺序来跳。一开始小美可以站在任意一个小方格。从一个方格跳到另一个方格的花费为两个方格的曼哈顿距离。小美想知道是否可以依照该顺序一直跳到 k，如果可以，最小的总花费是多少。

两个格子 $(x_1,y_1), (x_2,y_2)$ 的曼哈顿距离为横坐标之差+纵坐标之差，即 $|x_1-x_2|+|y_1-y_2|$，例如 $(3,4),(1,6)$ 的曼哈顿距离为 $|3-1|+|4-6|=4$。

输入格式

第一行输入两个正整数 $n,k$；

接下来输入一个 $n$ 行 $n$ 列的矩阵，表示这个方格。每一个数字都在 $1\sim k$ 的范围内。

输出格式

如果不可能完成，输出 -1；否则，输出最小的总花费。

样例

2 2
1 2
2 1

1

样例解释 1

小美从 (1,1) 跳到 (1,2)。

4 4
1 2 2 1
2 4 4 1
4 4 4 2
1 1 1 2

-1

数据范围

• 对于 30% 的数据，$1\le n \le 5$；
• 对于 60% 的数据，$1\le n \le 8$；
• 对于 100% 的数据，$1\le n \le 50, 1\le k \le n^2$

来源

by Vingying