31411번 - 대회 개최

문제

용범이는 보라매컵에 문제를 출제하기 위해 서로 다른 $N$가지 종류의 알고리즘 문제들을 각각 $K$개씩, 총 $N\times K$개의 문제를 만들었다. 그중 $i$번째 알고리즘의 $j$번째 문제의 난이도는 $d_{ij}$이다. 그러나 만든 문제를 모두 내기에는 대회 시간이 부족했기에, 서로 다른 $N$개의 알고리즘마다 각각 하나의 문제씩 총 $N$개의 문제만 내고자 한다.

또한 용범이는 문제의 난이도가 급격하게 상승하는 것을 방지하기 위해, 난이도 커브를 최소화하고자 한다. 난이도 커브는 대회의 $i$번 문제의 난이도를 $x_i$라 할 때 $\left\vert x_1 - x_2 \right\vert + \left\vert x_2 - x_3 \right\vert + \cdots + \left\vert x_{N-1} - x_N \right\vert$라고 정의한다. 단, $N = 1$일 때의 난이도 커브는 0ドル$으로 정의한다.

용범이를 도와 $N$개의 문제들의 순서를 적절히 배치할 때 난이도 커브의 최솟값을 구해주자.

입력

첫 번째 줄에 알고리즘의 개수 $N$과 알고리즘마다 만든 문제 개수 $K$가 공백으로 구분되어 주어진다. $(1 \le N,K \le 1,000円)$

이후 $N$개의 줄에 걸쳐, $i+1$번째 줄에 $i$번째 알고리즘의 $j$번째 문제의 난이도를 의미하는 정수 $d_{i1},\cdots,d_{iK}$가 공백으로 구분되어 주어진다. $(1 \le d_{ij} \le 100,000円)$

출력

$N$개의 문제들의 순서를 적절히 배치할 때 난이도 커브의 최솟값을 출력한다.

제한

힌트