휴가

시간 제한1초메모리 제한128 MB

요약

n개 명소의 순열을 정해 k개 순위와의 위치 차이를 8로 자른 값의 합이 최소가 되도록 한다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 정렬, 그리디
정답자: 아직 제출이 없습니다

문제

비타사르(Byteasar)는 바이트랜드(Byteland)로 휴가를 떠나려 합니다. 그는 여행 계획을 세우면서 어떤 관광 명소를 가장 보고 싶은지 정하려 합니다. 바이트랜드에는 여러 온라인 여행 안내서가 있고, 각 안내서에는 모든 명소의 순위가 실려 있습니다. 비타사르는 이 순위들을 참고하여 자신만의 순위를 만들고 싶어 합니다.

명소는 $1$ 번부터 $n$ 번까지 번호가 매겨져 있습니다. 하나의 순위란 $1$ 부터 $n$ 까지의 수를 가장 추천하는 명소부터 가장 덜 추천하는 명소 순으로 나열한 수열입니다.

두 순위 사이의 거리는 다음과 같이 계산합니다. 각 명소에 대해 두 순위에서 그 명소가 놓인 위치 $p_1$ , $p_2$ 를 찾고, 값 $\min(|p_1 - p_2|, 8)$ 을 구합니다. 이 값은 해당 명소에 대해 두 순위가 얼마나 다른지를 나타냅니다. 두 순위의 거리는 모든 명소에 대한 이 값들의 합입니다.

비타사르는 자신이 찾은 모든 온라인 순위와의 거리 합이 가능한 한 작아지는 자신만의 순위를 만들고자 합니다. 그가 만들 수 있는 최소 거리 합을 구하세요.

입력

첫째 줄에 두 정수 $n$ 과 $k$ 가 주어집니다 ( $2 \le n \le 5000$ , $2 \le k \le 3$ ). $n$ 은 바이트랜드에 있는 명소의 수이고, $k$ 는 비타사르가 찾은 온라인 안내서의 수입니다.

다음 $k$ 개의 줄에는 각각 하나의 온라인 순위가 주어집니다. 각 순위는 $1$ 부터 $n$ 까지의 정수를 각각 정확히 한 번씩 포함하는 $n$ 개의 정수 수열이며, 가장 추천하는 명소부터 가장 덜 추천하는 명소 순으로 나열되어 있습니다.

출력

비타사르의 순위와 그가 찾은 온라인 순위들 사이의 최소 거리 합을 정수 하나로 첫째 줄에 출력합니다.

힌트

최소 거리 합을 이루는 순위는 여러 개일 수 있지만, 출력해야 하는 값은 그 최소 거리 합(정수 하나)뿐입니다. 예를 들어 명소가 $5$ 개이고 순위가 5 2 4 3 1, 2 4 1 3 5로 주어지면, 2 4 5 3 1 또는 5 2 4 3 1과 같은 여러 순위가 모두 최소 거리 합 $8$ 을 달성합니다.

예제4

예제 1
입력
```
5 2
5 2 4 3 1
2 4 1 3 5
```
예상 출력
```
8
```
예제 2
입력
```
2 2
1 2
2 1
```
예상 출력
```
2
```
예제 3
입력
```
4 2
1 2 3 4
1 2 3 4
```
예상 출력
```
0
```

예제 4

입력

6 3
1 2 3 4 5 6
2 1 4 3 6 5
3 4 1 2 5 6

예상 출력