IMO

국제수학올림피아드(IMO)는 매년 개최되는 고등학생 대상 수학 대회이다. 2025년 IMO 대회는 EGOI와 같은 시기에 열린다. 여러분이 이 글을 읽는 현재, IMO의 두 대회일은 모두 끝났으며 채점도 아마 거의 완료되었을 것이다. EGOI와 같은 프로그래밍 대회와 달리 채점은 수작업으로 이루어지며, 이는 길고 고된 과정이다.

올해 IMO에는 $M$개의 문제(번호는 $0$부터 $M-1$까지)가 있었고, 각 문제의 최고 점수는 $K$점이다. 대회에는 $N$명의 참가자가 참가했다. $i$번째 참가자는 문제 $j$에서 $a_{i,j}$점을 받았으며, 여기서 $a_{i,j}$는 $0$ 이상 $K$ 이하의 정수이다. 참가자의 순위는 각 참가자의 총점으로 결정하며, 동점인 경우 참가자의 인덱스로 순위를 정한다. 더 형식적으로, 다음 중 하나를 만족하면 참가자 $x$의 순위가 참가자 $y$보다 높다:

• 참가자 $x$의 총점이 참가자 $y$의 총점보다 크거나,

• 두 참가자의 총점이 같고 $x < y$인 경우.

최종 순위를 발표하려면 주최 측은 값 $a_{i,j}$ 중 일부를 공개해야 한다. 어떤 값이 공개되지 않았다면, 그 값에 관해서는 $0$ 이상 $K$ 이하의 정수라는 사실만 알려진다.

주최 측은 값 $a_{i,j}$을 가능한 한 적게 공개하고자 한다. 동시에 모든 사람이 올바른 최종 순위를 알 수 있도록 해야 한다. 즉, 공개된 값들과 일치하는 순위가 올바른 순위뿐이도록 값들의 집합을 공개해야 한다.

참가자 전체의 순위를 유일하게 결정하도록 값 $a_{i,j}$ 중 $S$개를 공개할 수 있는 가장 작은 $S$를 구하여라.

제한 및 채점

• $2 \leq N \leq 20\,000$.

• $1 \leq M \leq 100$.

• $1 \leq K \leq 100$.

• $0 \leq i \leq N-1$이고 $0\leq j \leq M-1$인 모든 쌍 $i,j$에 대해 $0 \leq a_{i,j} \leq K$.

여러분의 풀이는 각각 일정한 점수가 배정된 테스트 그룹들의 집합으로 평가된다. 각 테스트 그룹은 테스트 케이스들의 집합을 포함한다. 한 테스트 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 해결해야 한다.

그룹   |   점수   |   제한

 1  |  10  |  $N = M = 2$ 및 $K = 1$

 2  |  13  |  $N = 2$

 3  |  10  |  $N \cdot M \leq 16$

 4  |  18  |  $K = 1$

 5  |  21  |  $N \leq 10\,000$ 및 $M,K \leq 10$

 6  |  28  |  추가 제한 없음

예제

첫 번째 예제에서는 $20$개의 점수를 다음과 같이 공개할 수 있다:

$7$  |  $7$  |  $0$  |  $\bullet$  |  $7$  |  $\bullet$

$7$  |  $3$  |  $0$  |  $7$  |  $2$  |  $1$

$\bullet$  |  $0$  |  $0$  |  $\bullet$  |  $0$  |  $0$

$7$  |  $7$  |  $7$  |  $7$  |  $7$  |  $1$

여기서 세 번째 참가자의 총점은 $0$ 이상 $14$ 이하인 것으로 알려져 있으며, 이는 확실히 다른 어떤 점수보다도 낮다. $20$개보다 적은 점수를 공개하는 것은 불가능함을 보일 수 있다. 예를 들어 세 번째 참가자의 영점 중 하나를 숨긴다면, 이 참가자의 총점은 최대 $21$점일 수 있다. 두 번째 참가자의 총점은 $20$점이지만 세 번째 참가자보다 반드시 높은 순위를 차지해야 하므로, 이는 문제가 된다.

첫 번째 예제는 테스트 그룹 $5$과 $6$의 제한을 만족한다.

두 번째 예제에서는 첫 번째 참가자의 유일한 점수만 공개하거나 두 번째 참가자의 유일한 점수만 공개할 수 있다(둘 다 공개할 수는 없다). 첫 번째 참가자의 점수만 공개하면 첫 번째 참가자의 총점이 $1$점임을 알 수 있다. 이는 두 번째 참가자의 점수 역시 $1$점이더라도 첫 번째 참가자의 인덱스가 더 작으므로 더 높은 순위를 차지한다는 뜻이다. 마찬가지로 두 번째 참가자의 점수만 공개하면 그 참가자의 점수가 영점임을 알 수 있으며, 따라서 첫 번째 참가자는 자신의 점수와 관계없이 더 높은 순위를 차지한다.

두 번째 예제는 테스트 그룹 $2$, $3$, $4$, $5$, $6$의 제한을 만족한다.

세 번째 예제는 테스트 그룹 $2$, $3$, $5$, $6$의 제한을 만족한다.

네 번째 예제는 모든 테스트 그룹의 제한을 만족한다.

첫 번째 줄에 참가자 수, 문제 수, 문제의 최고 점수를 각각 나타내는 세 정수 $N$, $M$, $K$가 주어진다.

이어서 $N$개의 줄이 주어지며, $i$번째 줄에는 $a_{i,j}$가 주어진다. 즉, 이 줄들 중 첫 번째 줄에는 $a_{0,0}, a_{0,1}, \ldots, a_{0, M-1}$가, 두 번째 줄에는 $a_{1,0}, a_{1,1}, \ldots, a_{1, M-1}$가 주어지고, 이와 같은 방식으로 계속된다.

최종 순위가 유일하게 결정되도록 공개할 수 있는 점수 개수의 최솟값을 나타내는 정수 하나 $S$를 출력한다.