cats 的 max

Problem Description

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

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

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

Input

第一行一个整数 $t$（$1\leq t\leq 1000$），表示总的数据个数。 接下来包含 $t$ 组数据，每组数据第一行三个整数 $n,m,k$（$1\leq k\leq n\leq 1000$ ，$1\leq m\leq 13$），依次表示矩阵 $a_{i,j}$ 的行数和列数以及可以选择的行数。 接下来的 $n$ 行，每行包含 $m$ 个整数，其中第 $i$ 行第 $j$ 列表示 $a_{i,j}$（$0\leq a_{i,j}\leq 10^9$）。 数据保证对于所有数据的 $n$ 的和不超过 $2\times 10^5$，且 $m$ 大于 $5$ 的数据的组数不超过 $10$ 组。

Output

共 $t$ 行，依次表示这 $t$ 组数据的结果。

Sample Input

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

Sample Output

11
12
22

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（6）