카니발 티켓

링고는 싱가포르의 카니발에 왔다. 가방에는 경품 게임 가판대에서 쓸 티켓이 들어 있다. 티켓은 $n$가지 색 중 하나를 가지며, 음이 아닌 정수가 하나씩 적혀 있다. 서로 다른 티켓에 적힌 정수가 같을 수도 있다. 카니발 규칙의 특이한 점 때문에 $n$은 항상 짝수임이 보장된다.

링고의 가방에는 각 색마다 티켓이 $m$장씩, 모두 $n \cdot m$장 들어 있다. 색 $i$의 $j$번째 티켓에는 정수 $x[i][j]$가 적혀 있다 ($0 \leq i \leq n-1$, $0 \leq j \leq m-1$).

경품 게임은 $k$라운드로 진행되며, 라운드 번호는 $0$부터 $k-1$까지다. 각 라운드는 다음 순서로 진행된다.

• 링고는 가방에서 각 색마다 티켓을 하나씩 골라 $n$장의 집합을 만든다. 그런 다음 이 집합을 진행자에게 건넨다.
• 진행자는 그 집합의 티켓에 적힌 정수 $a[0],\;a[1]\;\;\ldots\;\;a[n-1]$을 적어 둔다. 이 $n$개의 정수 순서는 중요하지 않다.
• 진행자는 행운의 추첨 상자에서 특별한 카드를 뽑아, 카드에 적힌 정수 $b$를 적어 둔다.
• 진행자는 $i$가 $0$부터 $n-1$까지일 때 $a[i]$와 $b$의 절댓값 차이를 계산한다. 이 절댓값 차이의 합을 $S$라고 하자.
• 이번 라운드에서 진행자는 링고에게 값이 $S$인 경품을 준다.
• 집합에 든 티켓은 버려지며 이후 라운드에서 쓸 수 없다.

$k$라운드가 끝난 뒤 링고의 가방에 남은 티켓은 버려진다.

자세히 관찰한 링고는 이 경품 게임이 조작되어 있다는 것을 알아냈다. 행운의 추첨 상자 안에는 사실 프린터가 있다. 진행자는 각 라운드마다 그 라운드 경품의 값을 최소로 만드는 정수 $b$를 찾는다. 진행자가 고른 값이 그 라운드의 특별한 카드에 인쇄된다.

이 모든 사실을 아는 링고는 티켓을 라운드에 배분하려고 한다. 즉, 경품의 총합을 최대로 만들기 위해 각 라운드에 쓸 티켓 집합을 정하려고 한다.

• $2 \leq n \leq 1500$이고 $n$은 짝수다.
• $1 \leq k \leq m \leq 1500$
• $0 \leq x[i][j] \leq 10^9$ (모든 $0 \leq i \leq n-1$, $0 \leq j \leq m - 1$에 대해)
• $x[i][j-1] \leq x[i][j]$ (모든 $0 \leq i \leq n-1$, $1 \leq j \leq m-1$에 대해)