BalticOI 2019 Day2 T3. Olympiads

题目描述

两个相邻的城市每年都会派出一个 $K$ 人的代表队参加 $K$ 场比赛。每一位参赛者都参加所有 $K$ 场比赛，单场比赛中代表队的得分是该比赛中代表队单名参赛者的最高分，而代表队的总得分是各场比赛代表队的得分之和。

举个 $K = 3$ 的例子：

该队在这三场比赛的总得分为 $7+5+6=18$。

两个城市之间已经不仅仅开始争论哪个城市有最好的代表队，而且争论哪个城市有第 $C$ 好的代表队。其中 $C=1$ 代表最好（即团队总分最高）的代表队，$C=2$ 代表第二好的代表队，以此类推。

你的任务是为其中一个城市找到他们城市中第 $C$ 好的代表队。两个代表队是不同的，当且仅当两个代表队中至少有一名成员不同。

输入格式

输入第一行包含三个整数 $N,K,C$，其中 $N$ 代表该城市的候选队员人数，$K$ 代表一个代表队的人数，$C$ 代表你要求出的是第 $C$ 好的代表队。

接下来 $N$ 行，每行包含 $K$ 个整数，其中第 $i$ 行第 $j$ 个数代表队员 $i$ 在第 $j$ 场比赛上的得分。

数据保证：$K \leq N$，可能的代表队组成方案数不少于 $C$，每名队员的得分不超过 $10^6$。

输出格式

输出包含一个整数，即该城市第 $C$ 好的代表队的得分。

样例

输入

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

输出

24

解释
一共有 $5$ 种组队方案，得分从高到低分别为：$26, 26, 25, 24, 22$。

数据范围与提示

各子任务的数据规模如下：

• 子任务 1（$13$ 分）：$1 \leq N \leq 500, 1 \leq K \leq 2, 1 \leq C \leq 2000$
• 子任务 2（$31$ 分）：$1 \leq N \leq 40, 1 \leq K \leq 6, 1 \leq C \leq 2000$
• 子任务 3（$24$ 分）：$1 \leq N \leq 500, 1 \leq K \leq 6, 1 \leq C \leq 2000$，且所有得分均不超过 $10$
• 子任务 4（$32$ 分）：$1 \leq N \leq 500, 1 \leq K \leq 6, 1 \leq C \leq 2000$