Description

Two neighboring cities send a team of $K$ people every year to compete in $K$ events. Each contestant participates in all $K$ events. In a single event, the team’s score is the highest score achieved by any single member of the team in that event. The team’s total score is the sum of the team scores over all events.

Here is an example with $K = 3$:

The total score of the team in these three events is $7 + 5 + 6 = 18$.

The two cities have started debating not only which city has the best team, but also which city has the $C$-th best team. Here, $C = 1$ means the best team (i.e., the team with the highest total score), $C = 2$ means the second best team, and so on.

Your task is to find, for one city, the score of the $C$-th best team in that city. Two teams are considered different if and only if they differ by at least one member.

Input Format

The first line contains three integers $N, K, C$, where $N$ is the number of candidate contestants in the city, $K$ is the team size, and $C$ indicates that you need to find the $C$-th best team.

The next $N$ lines each contain $K$ integers. In the $i$-th line, the $j$-th number is the score of contestant $i$ in event $j$.

It is guaranteed that $K \leq N$, the number of possible teams is at least $C$, and each contestant’s score does not exceed $10^6$.

Output Format

Output one integer: the score of the city’s $C$-th best team.

5 4 4
7 0 4 9
3 0 8 4
1 1 3 7
5 1 3 4
4 2 2 9

24

Hint

The constraints for each subtask are as follows:

• Subtask 1 (13 points): $1 \leq N \leq 500, 1 \leq K \leq 2, 1 \leq C \leq 2000$；
• Subtask 2 (31 points): $1 \leq N \leq 40, 1 \leq K \leq 6, 1 \leq C \leq 2000$；
• Subtask 3 (24 points): $1 \leq N \leq 500, 1 \leq K \leq 6, 1 \leq C \leq 2000$，and all scores do not exceed $10$；
• Subtask 4 (32 points): $1 \leq N \leq 500, 1 \leq K \leq 6, 1 \leq C \leq 2000$；

Translated by ChatGPT 5