310523: CF1846C. Rudolf and the Another Competition

C. Rudolf and the Another Competitiontime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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$.

Output

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

ExampleInput

5
3 3 120
20 15 110
90 90 100
40 40 40
2 1 120
30
30
1 3 120
10 20 30
3 2 27
8 9
10 7
10 8
3 3 15
7 2 6
7 5 4
1 9 8

Output

2
1
1
2
1

Note

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.

题目大意：
鲁道夫参加了一场遵循ICPC规则的编程比赛。规则规定，每解决一个问题，参赛者得到1分，并承担从比赛开始到解决问题时所经过的分钟数作为罚时。在最终排名中，得分最多的参赛者排名较高，如果得分相同，则罚时较低的参赛者排名较高。

总共有n名参赛者注册了比赛，鲁道夫是编号为1的参赛者。已知将有m个问题提出，比赛将持续h分钟。一个强大的人工智能预测了值$t_{i, j}$，表示第i个参赛者解决第j个问题将需要多少分钟。

鲁道夫意识到解决问题的顺序将影响最终结果。例如，如果$h = 120$，解决问题的耗时为[20, 15, 110]，那么如果鲁道夫按以下顺序解决问题：

- $3, 1, 2$，那么他将只解决第三个问题，得到1分和110罚时。
- $1, 2, 3$，那么他将在开始后20分钟解决第一个问题，35分钟解决第二个问题，并且没有时间解决第三个问题。因此，他将得到2分和55罚时。
- $2, 1, 3$，那么他将在开始后15分钟解决第二个问题，35分钟解决第一个问题，并且没有时间解决第三个问题。因此，他将得到2分和50罚时。

鲁道夫对他在比赛中获得的名次感兴趣，如果每个参赛者都根据人工智能的预测以最佳顺序解决问题的话。如果得分和罚时相同，鲁道夫将获得最好的名次。

输入输出数据格式：
输入：
- 第一行包含一个整数$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$。

输出：
- 对于每个测试用例，输出一个整数——如果所有参赛者都以最佳顺序解决问题，鲁道夫在最终排名中的名次。题目大意： 鲁道夫参加了一场遵循ICPC规则的编程比赛。规则规定，每解决一个问题，参赛者得到1分，并承担从比赛开始到解决问题时所经过的分钟数作为罚时。在最终排名中，得分最多的参赛者排名较高，如果得分相同，则罚时较低的参赛者排名较高。 总共有n名参赛者注册了比赛，鲁道夫是编号为1的参赛者。已知将有m个问题提出，比赛将持续h分钟。一个强大的人工智能预测了值$t_{i, j}$，表示第i个参赛者解决第j个问题将需要多少分钟。 鲁道夫意识到解决问题的顺序将影响最终结果。例如，如果$h = 120$，解决问题的耗时为[20, 15, 110]，那么如果鲁道夫按以下顺序解决问题： - $3, 1, 2$，那么他将只解决第三个问题，得到1分和110罚时。 - $1, 2, 3$，那么他将在开始后20分钟解决第一个问题，35分钟解决第二个问题，并且没有时间解决第三个问题。因此，他将得到2分和55罚时。 - $2, 1, 3$，那么他将在开始后15分钟解决第二个问题，35分钟解决第一个问题，并且没有时间解决第三个问题。因此，他将得到2分和50罚时。 鲁道夫对他在比赛中获得的名次感兴趣，如果每个参赛者都根据人工智能的预测以最佳顺序解决问题的话。如果得分和罚时相同，鲁道夫将获得最好的名次。 输入输出数据格式： 输入： - 第一行包含一个整数$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$。 输出： - 对于每个测试用例，输出一个整数——如果所有参赛者都以最佳顺序解决问题，鲁道夫在最终排名中的名次。