#216088. [ICPC 2020 NAC] Hopscotch

There’s a new art installation in town, and it inspires you... to play a childish game. The art installation consists of a floor with an matrix of square tiles. Each tile holds a single number from to . You want to play hopscotch on it. You want to start on some tile numbered , then hop to some tile numbered , then , and so on, until you reach some tile numbered . You are a good hopper, so you can hop any required distance. You visit exactly one tile of each number from to .

What’s the shortest possible total distance over a complete game of Hopscotch? Use the Manhattan distance: the distance between the tile at and the tile at is .

The first line of input contains two space-separated integers () and (), where the art installation consists of an matrix with tiles having numbers from to .

Each of the next lines contains space-separated integers (). This is the art installation.

Output a single integer, which is the total length of the shortest path starting from some tile and ending at some tile, or if it isn’t possible.

样例输入 1

10 5
5 1 3 4 2 4 2 1 2 1
4 5 3 4 1 5 3 1 1 4
4 2 4 1 5 4 5 2 4 1
5 2 1 5 5 3 5 2 3 2
5 5 2 3 2 3 1 5 5 5
3 4 2 4 2 2 4 4 2 3
1 5 1 1 2 5 4 1 5 3
2 2 4 1 2 5 1 4 3 5
5 3 2 1 4 3 5 2 3 1
3 4 2 5 2 5 3 4 4 2

样例输出 1

5

样例输入 2

10 5
5 1 5 4 1 2 2 4 5 2
4 2 1 4 1 1 1 5 2 5
2 2 4 4 4 2 4 5 5 4
2 4 4 5 5 5 2 5 5 2
2 2 4 4 4 5 4 2 4 4
5 2 5 5 4 1 2 4 4 4
4 2 1 2 4 4 1 2 4 5
1 2 1 1 2 4 4 1 4 5
2 1 2 5 5 4 5 2 1 1
1 1 2 4 5 5 5 5 5 5

样例输出 2

-1