Walktober

John은 Walktober라는 연례 걷기 대회에 참가한다. 대회는 총 $\mathbf{N}$일 동안 진행되며, $\mathbf{N}$일 모두에 대해 참가자들의 일일 걸음 수를 기록한다. 각 참가자에게는 $1$부터 $\mathbf{M}$까지 범위의 고유한 ID가 할당되며, 여기서 $\mathbf{M}$는 등록된 참가자의 총수이다. 각 참가자의 일일 걸음 수를 기록하는 전체 순위표가 유지된다.

John은 올해 Walktober에서 우승하기로 결심했으며, 그의 목표는 $\mathbf{N}$일 각각에 모든 참가자 중 최대 일일 걸음 수를 기록하는 것이다. 작년에도 Walktober에 참가했던 그는 자신의 목표를 달성하려면 몇 걸음이 부족했는지 알고 싶었다. 전년도 순위표가 주어질 때, 매일 최대 일일 걸음 수를 기록한다는 목표를 달성하기 위해 작년 기록에 더 필요했던 최소 추가 걸음 수를 계산한다.

제한

메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. $1 \le \mathbf{N} \le 31$. 모든 $i$ 및 $j$에 대해 $1 \le \mathbf{S_{i,j}} \le 60000$. $1 \le \mathbf{P} \le \mathbf{M}$.

테스트 세트 1

시간 제한: 20초. $\mathbf{M} = 2$.

테스트 세트 2

시간 제한: 40초. $2 \le \mathbf{M} \le 1000$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 참가자의 총수, 대회가 진행되는 총일수, 그리고 John의 전년도 참가자 ID of John를 나타내는 세 정수 $\mathbf{M}$, $\mathbf{N}$, $\mathbf{P}$가 주어진다. 다음 $\mathbf{M}$개의 줄은 전년도 순위표를 나타내며, 각 줄에는 $\mathbf{N}$개의 정수가 주어진다. $i$번째 줄의 $j$번째 정수는 대회의 $j$번째 날에 ID가 $i$인 참가자의 걸음 수 $\mathbf{S_{i,j}}$를 나타낸다.

각 테스트 케이스마다 Case #$x$: $y$를 포함하는 한 줄을 출력한다. 여기서 $x$는 (1부터 시작하는) 테스트 케이스 번호이고, $y$는 John이 목표를 달성하는 데 필요한 최소 총 추가 걸음 수이다.

예제 케이스에서 대회는 $3$일 동안 진행되었고, 참가자 ID of John는 $1$였다. $1$번째 날에는 다른 참가자의 걸음 수가 더 많으므로 John에게 $500$걸음이 추가로 필요하다. 나머지 날에는 John이 이미 최대 걸음 수를 기록했으므로 추가 걸음이 필요하지 않다. 따라서 목표를 달성하려면 총 $500$걸음이 추가로 필요하다.

추가 예제 - 테스트 세트 2

예제 케이스 #1에서 대회는 $2$일 동안 진행되었고, 참가자 ID of John는 $3$였다. 목표를 달성하려면 $1$번째 날에 $1000$걸음, $2$번째 날에 $0$걸음이 추가로 필요하다. 따라서 목표를 달성하려면 총 $1000$걸음이 추가로 필요하다.

예제 케이스 #2에서 대회는 $3$일 동안 진행되었고, 참가자 ID of John는 $2$였다. 목표를 달성하려면 $1$번째 날에 $0$걸음, $2$번째 날에 $2000$걸음, 그리고 $3$번째 날에 $500$걸음이 추가로 필요하다. 따라서 목표를 달성하려면 총 $2500$걸음이 추가로 필요하다.