Baltic Olympiad in Informatics: 2019 Day 2, Problem 3

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 they can send to the competition. The cities have started arguing about not only which city has the best team, but also about which city has the better ~C~-th best team for some integer ~C~, where ~C = 1~ corresponds to the best team, ~C = 2~ is the second best team, and so on.

You are tasked with helping one of the cities finding out the expected score its ~C~-th best team, considering all the different ~K~-member teams they could compose from their eligible contestants.

Two teams are considered different if they have at least one contestant different.

Input Specification

The first line contains the integers ~N~, ~K~, and ~C~, where ~N~ is the total number of eligible contestants in a city, ~K~ the size of the team ~(K \le N)~, and ~C~ the index of the team we're 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 will be greater than ~10^6~.

Output Specification

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

Sample Input

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

Sample Output

24

There are ~5~ possible teams and they would score ~26~, ~26~, ~25~, ~24~, and ~22~ points, so the ~4~-th best score is ~24~.

Grading

The test groups satisfy the following conditions:

1. (~13~ points) ~1 \le N \le 500~, ~1 \le K \le 2~, ~1 \le C \le 2\,000~.
2. (~31~ points) ~1 \le N \le 100~, ~1 \le K \le 6~, ~1 \le C \le 2\,000~.
3. (~24~ points) ~1 \le N \le 500~, ~1 \le K \le 6~, ~1 \le C \le 2\,000~, no score is greater than ~10~.
4. (~32~ points) ~1 \le N \le 500~, ~1 \le K \le 6~, ~1 \le C \le 2\,000~.