Olympiads

Two neighbouring cities send each year a team of $K$ contestants to compete in $K$ different events. Each contestant participates in all the events. The score of a team in an event is the highest score earned by any of that team's contestants in that event. The total score of a team is the sum of the scores of the team over all events. For example, if $K = 3$ and the contestants score $(4, 5, 3)$, $(7, 3, 6)$, and $(3, 4, 5)$, then the scores for the team in the events are $(7, 5, 6)$ and the total score of the team is $18$.

Each city has a set of eligible contestants it can send to the competition. The cities argue about which city has the best team and also about which city has the $C$-th best team, where $C = 1$ corresponds to the best team, $C = 2$ to the second best team, and so on.

You are tasked with helping one of the cities find the expected total score of its $C$-th best team, considering all the different $K$-member teams it could compose from its eligible contestants. Two teams are considered different if at least one contestant differs.

The first line contains the integers $N$, $K$, and $C$, where $N$ is the total number of eligible contestants in a city, $K$ is the size of the team ($K \le N$), and $C$ is the index of the team we are interested in ($C$ does not exceed the number of possible $K$-member teams).

Each of the following $N$ lines contains $K$ non-negative integers, the expected scores of one eligible contestant in the $K$ events. No score is greater than $10^6$.

The only line should contain the total score of the $C$-th best team.