4-6 Rudolf and the Another Competition

4-6 Rudolf and the Another Competition

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Rudolf and the Another Competition

链接:https://codeforces.com/contest/1846/problem/C
来源:codeforces

时间限制:1 seconds
空间限制:256 megabytes

题目描述

鲁道夫已经报名参加了一个遵循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\)分钟后解决第一个问题,在\(20+15=35\)分钟后再解决第二个问题,并且他将没有时间解决第三个问题。因此,他将获得\(2\)的积分和\(20+35=55\)的罚时。

\({2,1,3}\),那么他将在从开始的\(15\)分钟后解决第二个问题,在\(15+20=35\)分钟之后解决第一个问题,并且他将没有时间解决第三个问题。因此,他将获得\(2\)的积分和\(15+35=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\)。

输出

对于每个测试案例,输出一个整数--如果所有参与者都按最佳顺序解决问题,那么鲁道夫最后在比赛结束能达到多少名。

样例

输入样例

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

输出样例

2
1
1
2
1

样例解释

在第一个例子中,鲁道夫将得到\(2\)分和\(50\)分钟的罚时。第二个参与者只解决了一个问题,得到\(1\)分和\(90\)分钟的罚时。而第三位参与者将解决所有的\(3\)个问题,得到\(3\)分和\(240\)分钟的惩罚。因此,鲁道夫将获得第二名。

在第二个例子中,两个参与者都将得到\(1\)分和\(30\)分钟的罚时。在积分相同的情况下,鲁道夫得到的名次更好,所以他将获得第一名。

在第三个例子中,鲁道夫是唯一的参赛者,所以他将获得第一名。

在第四个例子中,所有参与者都能解决两个问题,罚时分别为\(25 = 8 + (8 + 9)\)、\(24 = 7 + (7 + 10)\)和\(26 = 8 + (8 + 10)\),由于罚时,第二个参与者得到了第一名,而鲁道夫得到了第二名。

2023暑假集训7月8日训练题

未参加
状态
已结束
规则
ACM/ICPC
题目
6
开始于
2023-07-08 09:00
结束于
2023-07-08 11:00
持续时间
2.0 小时
主持人
参赛人数
22