8600: Fall Guys-Perfect Match

In the famous game "Fall Guys:Ultimate Knockout", there's a level called "Perfect Match". We have simplified the rule of the game as follows: You stand on an n×n grid and there are m kinds of fruits. Also, each grid is labeled with some kind of fruit. It is guaranteed that each kind of fruit appears on at least 1 and at most 20 grids. You can choose to stand on any grid initially, then a fruit will appear on the big screen in the game, you need to run to a grid such that the fruit labeled on it is the same as the fruit on the screen, within the countdown. In the game, you can only move horizontally or vertically, i.e. if you stand on (x₁,y₁) and move to (x₂,y₂), the distance you move is ∣x₁−x₂∣+∣y₁−y₂∣.

You want to select a grid to stand on initially, to minimize the distance you need to move in the worst case of all m possible fruits to appear on the big screen, so that hopefully you will not be knocked out even in the worst case! Calculate this minimized distance.

The first line contains two integers n,m(1≤n≤1000,1≤m≤n²), denoting the size of the grid and the kinds of fruits, respectively.
The n lines follow, where the i-th line contains n integers a_i,1,a_i,2,...,a_i,n(1≤a_i,j≤m), denoting the fruits on the $i$-th row of the n×n grid.
It is guaranteed that for each 1≤x≤m, x appears at least 1 and at most 20 times in the matrix a.

Output an integer in one line, denoting the answer.

2 3
1 2
1 3

1