창고 컨테이너 재배열

한 회사가 N개의 매장을 운영하며 M가지 서로 다른 제품을 판매한다. 제품은 1부터 M까지의 번호로 구분한다. 창고에서는 각 제품을 매장 수만큼 담아 두므로, 각 제품 번호가 붙은 컨테이너가 정확히 N개씩 있고 컨테이너는 모두 N×M개이다. 창고가 좁아 컨테이너들은 한 줄로 놓여 있으며, 위치는 1번부터 N×M번까지이다. 마지막 위치인 N×M+1번은 컨테이너가 없는 빈 자리 하나이다.

배송을 빠르게 하기 위해, 관리자는 줄의 앞에서부터 M개씩 묶은 각 구간(위치 1..M, M+1..2M, ...)이 서로 다른 M개의 제품 번호(각 제품 하나씩)를 담도록 재배열하려 한다. 한 구간 안에서의 순서는 상관없다.

재배열은 오직 빈 자리를 이용해서만 한다. 한 번의 이동은 어떤 위치에 있는 컨테이너 하나를 현재 비어 있는 자리로 옮기는 것이며, 옮긴 뒤에는 원래 있던 위치가 빈 자리가 된다. 모든 이동이 끝난 뒤 빈 자리는 다시 N×M+1번 위치에 있어야 한다.

필요한 이동 횟수의 최솟값을 구하여라.

첫째 줄에 두 정수 N과 M이 주어진다 (1 ≤ N ≤ 400, 1 ≤ M ≤ 400). 둘째 줄에는 컨테이너의 초기 배열을 나타내는 N×M개의 정수가 왼쪽부터 순서대로 주어진다. 각 제품 번호 x (1 ≤ x ≤ M)는 정확히 N번 나타난다.

앞에서부터 M개씩 묶은 모든 구간이 서로 다른 M개의 제품 번호를 담고, 빈 자리가 다시 N×M+1번 위치로 돌아오도록 만드는 데 필요한 최소 이동 횟수를 정수 하나로 출력한다.