해킹

이바일로는 매주 다음과 같은 규칙으로 진행되는 정보학 대회에 참가한다.

참가자들에게는 풀어야 할 $N$개의 문제가 주어진다. 문제 하나를 풀면 참가자들은 그 문제를 채점 시스템에 제출한다. 대회 중에는 예비 테스트라고 불리는 작은 테스트 묶음으로 채점이 이루어진다. 예비 테스트 결과는 채점 직후 참가자에게 알려진다. 프로그램이 모든 테스트에서 정답을 내면, 참가자는 해당 문제에 대한 예비 점수를 받는다. 그런 다음 참가자는 그 문제를 잠가서 다른 참가자들의 해당 문제 풀이를 볼 수 있다.

참가자는 다른 참가자의 풀이를 해킹할 수 있다. 이 경우 해킹된 풀이는 작성자에게 점수를 전혀 주지 못하고, 해킹한 풀이는 100점을 받는다. 해킹되지 않은 풀이가 대회 종료 후 전체 테스트 묶음을 통과하면, 참가자는 그 문제에서 미리 얻은 점수를 받는다. 대회가 끝나면 각 참가자가 문제 풀이와 해킹으로 얻은 총점이 계산된다. 가장 많은 점수를 얻은 참가자가 우승자다.

대회 종료까지 5분밖에 남지 않았다. 이바일로는 자신이 풀 수 있는 모든 문제를 이미 풀었고(그의 풀이는 대회 종료 후 전체 테스트 묶음을 통과한다), 그 문제들을 잠가 두었다. 이제 그는 다른 참가자들의 풀이를 해킹하는 것만으로 순위를 올릴 수 있다.

이바일로의 코치는 그가 단독 1위를 차지할 것을 요구한다. 이바일로가 1위가 아니거나 다른 참가자와 공동 1위를 차지하면 벌을 받는다. 즉 몇 가지 컴퓨터 게임을 할 기회를 박탈당한다. 당연히 이바일로는 조금 게을러서, 원하는 결과를 최소한의 노력으로 이루려고 한다.

여러분은 이바일로가 단독 1위를 차지하기 위해 해야 하는 최소 해킹 횟수를 구하는 프로그램 hacks를 작성해 그를 도울 수 있다. 1위를 차지하는 것이 불가능하면 $-1$을 출력한다.

이바일로는 어떤 참가자의 어떤 풀이든 해킹할 수 있고, 그가 해킹하지 않은 모든 풀이는 전체 테스트 묶음을 통과해 해당 참가자에게 점수를 준다고 가정한다. 이바일로는 프로그래밍을 너무 잘해서 해킹을 즉시 수행할 수 있다. 즉 남은 5분 동안 무한히 많은 문제를 해킹할 수 있다. 이바일로는 자신이 직접 푼 문제의 다른 참가자 풀이만 해킹할 수 있다.

표준 입력의 첫째 줄에는 문제 수 $N$, 참가자 수 $M$, 현재 순위표에서 이바일로의 번호 $K$가 주어진다(순위표는 참가자의 예비 점수로 정렬되어 있지 않다).

다음 $M$개 줄에는 각각 $N$개의 정수가 주어진다. 이 줄들 중 $i$번째 줄($i = 1, \ldots, M$)에는 $i$번째 참가자의 문제 $j$에 대한 예비 점수 $A_{ij}$($j = 1, \ldots, N$)가 주어진다. $A_{ij} = 0$이면 그 참가자가 아직 문제 $j$를 제출하지 않았거나 그의 풀이가 예비 테스트를 통과하지 못했음을 뜻한다.

표준 출력의 첫째 줄에 이바일로가 단독 1위를 차지하기 위해 해야 하는 최소 해킹 횟수를 하나의 정수로 출력하거나, 불가능하면 $-1$을 출력한다.

• $1 \le N \le 50$
• $1 \le M \le 10\,000$
• $1 \le K \le M$
• $0 \le A_{ij} \le 10\,000\,000$

첫 번째 예제에서 이바일로는 두 번째 참가자의 첫 번째 문제 풀이를 해킹할 수 있다. 그러면 100점을 얻어 $480 + 500 + 490 + 100 = 1\,570$점으로 1위가 된다.

두 번째 예제에서 이바일로는 두 참가자의 풀이를 해킹해야 한다. 그러면 $500 + 500 + 500 + 500 + 200 + 100 + 100 = 2400$점을 얻어 1위가 된다.

세 번째 예제에서 이바일로는 점수를 전혀 얻을 수 없다. 어떤 참가자도 어떤 문제도 풀지 않아 모든 참가자가 공동 1위이기 때문이다. 따라서 답은 $-1$이다.