题目描述 两个相邻的城市每年都会派出一个 K 人的代表队参加 K 场比赛。每一位参赛者都参加所有 K 场比赛,单场比赛中代表队的得分是该比赛中代表队单名参赛者的最高分,而代表队的总得分是各场比赛代表队的得分之和。
举个 K = 3 的例子:
比赛1 比赛2 比赛3
参赛者1 4 5 3
参赛者2 7 3 6
参赛者3 3 4 5
团队得分 7 5 6
该队在这三场比赛的总得分为 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$