杭电/2025-6/1008：cats 的 max

题目描述

cats 给出了一个 $n \times m$ 的矩阵 $a_{i,j}$。现在 cats 要在这 $n$ 行中选出 $k$ 行，假设选出的行编号依次为 $p_1,p_2,\dots,p_k$（序列 $p$ 中元素各不相同，且都在 $[1,n]$ 中），定义该方案的权值为：

$$\sum_{i=1}^{m}\left(\max\{a_{p_1,i},a_{p_2,i},\dots,a_{p_k,i}\}\right)$$

cats 想知道所有选择方案中权值的最大值。

输入输出格式

输入

第一行一个整数 $t$，表示数据组数。

接下来包含 $t$ 组数据。每组数据第一行三个整数 $n,m,k$，表示矩阵 $a_{i,j}$ 的行数、列数以及可选择的行数。

接下来的 $n$ 行，每行包含 $m$ 个整数，其中第 $i$ 行第 $j$ 列表示 $a_{i,j}$。

输出

输出共 $t$ 行，依次表示每组数据的答案。

样例

3
3 4 2
3 2 2 2
1 4 1 1
4 1 1 1
3 3 2
1 1 1
1 2 3
3 4 5
5 3 4
1 1 4
5 1 4
1 9 1
9 8 1
2 3 3

11
12
22

数据范围

• $1 \le t \le 1000$
• $1 \le k \le n \le 1000$
• $1 \le m \le 13$
• $0 \le a_{i,j} \le 10^9$
• 所有数据中 $n$ 的总和不超过 $2 \times 10^5$
• $m > 5$ 的数据组数不超过 $10$