컨테이너 줄 세우기

엔로고니아의 주요 수출품인 통나무를 담은 컨테이너가 항구의 화물 터미널에 놓여 있다. 컨테이너는 모두 크기가 같은 정육면체다. 터미널에는 컨테이너가 $L$개의 줄과 $C$개의 열로 놓여 있어 전부 $LC$개다. 컨테이너마다 $1$부터 $LC$까지 서로 다른 번호가 하나씩 붙어 있다.

$L$개의 줄은 각각 다른 배에 실린다. 도착한 나라에서 짐을 내리기 쉽도록, 한 줄에 놓인 컨테이너의 번호는 왼쪽에서 오른쪽으로 갈수록 커져야 한다. 정확히 말하면 첫째 줄에는 $1$번부터 $C$번까지, 둘째 줄에는 $C+1$번부터 $2C$번까지가 커지는 순서로 놓여야 하고, 이런 식으로 마지막 줄에는 $(L-1)C+1$번부터 $LC$번까지가 놓여야 한다. 그림 (a)는 줄이 5개, 열이 4개인 화물의 올바른 배치다.

크레인은 줄 두 개를 통째로 맞바꾸거나 열 두 개를 통째로 맞바꾼다. 그 밖의 방식으로 컨테이너 여러 개를 옮기거나 컨테이너 하나만 옮기지는 못한다.

선적 전날 밤, 인부들이 임금이 낮다고 항의하면서 크레인을 움직여 줄과 열을 맞바꿨다. 그림 (b)는 1번 줄과 4번 줄을 맞바꾼 뒤의 배치이고, 그림 (c)는 거기서 2번 열과 3번 열을 한 번 더 맞바꾼 뒤의 배치다.

선적은 오늘 해야 하므로 그 전에 컨테이너를 위에서 설명한 배치로 되돌려야 한다. 항의가 끝난 뒤의 컨테이너 위치가 주어질 때, 크레인만 써서 모든 컨테이너를 제자리로 되돌릴 수 있는지 판별하는 프로그램을 작성하라. 되돌릴 수 있다면 필요한 줄 맞바꿈 횟수와 열 맞바꿈 횟수의 합이 최소가 되도록 하는 값도 함께 구한다.

첫째 줄에 화물의 줄 수 $L$과 열 수 $C$가 주어진다. 다음 $L$개의 줄에는 항의가 끝난 뒤의 배치가 주어진다. 각 줄에는 정수 $C$개 $X_{l,1}, X_{l,2}, \dots, X_{l,C}$가 주어지며, $X_{l,c}$는 $l$번 줄 $c$번 열에 놓인 컨테이너의 번호다. $1$부터 $LC$까지의 정수가 각각 정확히 한 번씩 나타난다.

제한

• $1 \le L \le 300$
• $1 \le C \le 300$
• $1 \le X_{l,c} \le LC$

컨테이너를 모두 제자리로 되돌리는 데 필요한 줄 맞바꿈 횟수와 열 맞바꿈 횟수의 합의 최솟값을 한 줄에 출력한다. 크레인만 써서는 제자리로 되돌릴 수 없으면 그 줄에 * 문자만 출력한다.