CF1846C.Rudolf and the Another Competition

Rudolf has registered for a programming competition that will follow the rules of ICPC. The rules imply that for each solved problem, a participant gets $1$ point, and also incurs a penalty equal to the number of minutes passed from the beginning of the competition to the moment of solving the problem. In the final table, the participant with the most points is ranked higher, and in case of a tie in points, the participant with the lower penalty is ranked higher.

In total, $n$ participants have registered for the competition. Rudolf is a participant with index $1$. It is known that $m$ problems will be proposed. And the competition will last $h$ minutes.

A powerful artificial intelligence has predicted the values $t_{i, j}$, which represent the number of minutes it will take for the $i$-th participant to solve the $j$-th problem.

Rudolf realized that the order of solving problems will affect the final result. For example, if $h = 120$, and the times to solve problems are [$20, 15, 110$], then if Rudolf solves the problems in the order:

• ${3, 1, 2}$, then he will only solve the third problem and get $1$ point and $110$ penalty.
• ${1, 2, 3}$, then he will solve the first problem after $20$ minutes from the start, the second one after $20+15=35$ minutes, and he will not have time to solve the third one. Thus, he will get $2$ points and $20+35=55$ penalty.
• ${2, 1, 3}$, then he will solve the second problem after $15$ minutes from the start, the first one after $15+20=35$ minutes, and he will not have time to solve the third one. Thus, he will get $2$ points and $15+35=50$ penalty.

Rudolf became interested in what place he will take in the competition if each participant solves problems in the optimal order based on the predictions of the artificial intelligence. It will be assumed that in case of a tie in points and penalty, Rudolf will take the best place.

鲁道夫报名参加了一场遵循 ICPC 规则的编程竞赛。规则规定：每成功解决一道题，参赛者获得 $1$ 分，同时产生一个罚时，其值等于从比赛开始到该题被解决时刻所经过的分钟数。在最终排行榜中，得分更高的参赛者排名更靠前；若得分相同，则罚时更小的参赛者排名更靠前。

总共有 $n$ 名参赛者报名参赛，鲁道夫的编号为 $1$。已知比赛中将给出 $m$ 道题目，比赛总时长为 $h$ 分钟。

一个强大的人工智能已预测出数值 $t_{i, j}$，表示第 $i$ 名参赛者解决第 $j$ 道题所需的时间（单位：分钟）。

鲁道夫意识到，解题顺序会影响最终成绩。例如，若 $h = 120$，且各题解决时间分别为 $[20, 15, 110]$，那么当鲁道夫按如下顺序解题时：

• ${3, 1, 2}$：他仅能完成第 $3$ 题，获得 $1$ 分，罚时为 $110$；
• ${1, 2, 3}$：他在比赛开始后 $20$ 分钟完成第 $1$ 题，在 $20+15=35$ 分钟完成第 $2$ 题，但剩余时间不足以完成第 $3$ 题。因此他获得 $2$ 分，罚时为 $20+35=55$；
• ${2, 1, 3}$：他在比赛开始后 $15$ 分钟完成第 $2$ 题，在 $15+20=35$ 分钟完成第 $1$ 题，同样无法完成第 $3$ 题。因此他获得 $2$ 分，罚时为 $15+35=50$。

鲁道夫很想知道：如果每位参赛者均按照人工智能的预测，以最优顺序解题，他在最终排行榜中将排第几名？特别地，若出现得分与罚时均相同的并列情况，鲁道夫将获得其中最靠前的名次。

The first line contains an integer $t$ ($1 \le t \le 10^3$) — the number of test cases.

Then follow the descriptions of the test cases.

The first line of each test case contains three integers $n, m, h$ ($1 \le n \cdot m \le 2 \cdot 10^5, 1 \le h \le 10^6$) — the number of participants, the number of problems, and the duration of the competition, respectively.

Then there are $n$ lines, each containing $m$ integers $t_{i, j}$ ($1 \le t_{i, j} \le 10^6$) — the number of minutes it will take for the $i$-th participant to solve the $j$-th problem.

The sum of $n \cdot m$ over all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^3$）—— 测试用例的数量。

接下来是各测试用例的描述。

每个测试用例的第一行包含三个整数 $n, m, h$（$1 \le n \cdot m \le 2 \cdot 10^5, 1 \le h \le 10^6$）—— 分别表示参赛者人数、题目数量和比赛时长。

随后有 $n$ 行，每行包含 $m$ 个整数 $t_{i, j}$（$1 \le t_{i, j} \le 10^6$）—— 表示第 $i$ 位参赛者解决第 $j$ 道题目所需的分钟数。

所有测试用例中 $n \cdot m$ 的总和不超过 $2 \cdot 10^5$。

For each test case, output an integer — Rudolf's place in the final table if all participants solve problems in the optimal order.

对于每个测试用例，输出一个整数——如果所有参赛者都以最优顺序解题，则鲁道夫在最终排行榜上的名次。

In the first example, Rudolf will get $2$ points and $50$ penalty minutes. The second participant will solve only one problem and get $1$ point and $90$ penalty minutes. And the third participant will solve all $3$ problems and get $3$ points and $240$ penalty minutes. Thus, Rudolf will take the second place.

In the second example, both participants will get $1$ point and $30$ penalty minutes. In case of a tie in points, Rudolf gets the better position, so he will take the first place.

In the third example, Rudolf is the only participant, so he will take the first place.

In the fourth example, all participants can solve two problems with penalty of $25 = 8 + (8 + 9)$, $24 = 7 + (7 + 10)$ and $26 = 8 + (8 + 10)$, respectively, thanks to the penalty, the second participant gets the first place, and Rudolf gets the second.

在第一个例子中，鲁道夫将获得 $2$ 分和 $50$ 分钟罚时。第二位参赛者仅解决一个问题，获得 $1$ 分和 $90$ 分钟罚时。第三位参赛者将解决全部 $3$ 个问题，获得 $3$ 分和 $240$ 分钟罚时。因此，鲁道夫将获得第二名。

在第二个例子中，两位参赛者均获得 $1$ 分和 $30$ 分钟罚时。当分数相同时，鲁道夫获得更优的名次，因此他将获得第一名。

在第三个例子中，鲁道夫是唯一的参赛者，因此他将获得第一名。

在第四个例子中，所有参赛者均可解决两个问题，罚时分别为 $25 = 8 + (8 + 9)$、$24 = 7 + (7 + 10)$ 和 $26 = 8 + (8 + 10)$。由于罚时更少，第二位参赛者获得第一名，鲁道夫获得第二名。