Hopscotch 50

도시에 새 예술 작품이 설치되었고, 그것은 당신에게 유치한 놀이를 하고 싶게 만든다. 예술 작품은 n×n 개의 정사각형 타일로 이루어진 바닥이다. 각 타일에는 1부터 k까지의 수 하나가 적혀 있다. 당신은 그 위에서 hopscotch를 하려고 한다. 어떤 1번 타일에서 시작해 어떤 2번 타일로, 그다음 3번 타일로, 이런 식으로 k번 타일에 도달할 때까지 뛰어간다. 당신은 뛰어난 hopper라서 필요한 만큼 멀리 뛸 수 있다. 1부터 k까지의 각 수에 해당하는 타일을 정확히 하나씩 방문한다.

완전한 Hopscotch 게임에서 가능한 총 이동 거리의 최솟값은 얼마인가? 맨해튼 거리를 사용한다. (x1, y1) 타일과 (x2, y2) 타일 사이의 거리는 |x1 − x2| + |y1 − y2|이다.

입력의 첫 줄에는 두 정수 n (1 ≤ n ≤ 50)과 k (1 ≤ k ≤ n2)가 공백으로 구분되어 주어진다. 예술 작품은 1부터 k까지의 수가 적힌 타일로 이루어진 n×n 행렬이다.

다음 n개 줄 각각에는 n개의 정수 x (1 ≤ x ≤ k)가 공백으로 구분되어 주어진다. 이것이 예술 작품이다.

어떤 1번 타일에서 시작해 어떤 k번 타일에서 끝나는 최단 경로의 총 길이를 정수 하나로 출력한다. 불가능하면 −1을 출력한다.