← 返回题目列表

Codeforces · 1846/C

C. 鲁道夫和另一场比赛

中文机器翻译题面 查看原题

Rudolf 已报名参加遵循 ICPC 规则的编程竞赛。规则意味着,对于每个解决的问题,参与者将获得 $$$1$$$ 分,并且还会受到相当于从比赛开始到解决问题所经过的分钟数的惩罚。在决赛桌中,得分最高的参赛者排名靠前,如果积分相同,则罚分较低的参赛者排名靠前。

共有 $$$n$$$ 名参与者报名参加比赛。 Rudolf 是索引为 $$$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$$$。

输出

对于每个测试用例,输出一个整数 - 如果所有参与者都以最佳顺序解决问题,则鲁道夫在最终表中的位置。

示例

输入 #1

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

输出 #1

2
1
1
2
1

注意

在第一个示例中,Rudolf 将获得 $$$2$$$ 积分和 $$$50$$$ 罚分。第二名参与者只需解决一个问题,即可获得 $$$1$$$ 分和 $$$90$$$ 罚分。第三位参与者将解决所有 $$$3$$$ 问题并获得 $$$3$$$ 积分和 $$$240$$$ 罚分。因此,鲁道夫将获得第二名。

在第二个示例中,两个参与者都将获得 $$$1$$$ 积分和 $$$30$$$ 罚分。如果积分相同,鲁道夫的位置更好,因此他将获得第一名。

在第三个示例中,鲁道夫是唯一的参与者,因此他将获得第一名。

在第四个例子中,所有参与者都可以分别以$$$25 = 8 + (8 + 9)$$$、$$$24 = 7 + (7 + 10)$$$和$$$26 = 8 + (8 + 10)$$$的惩罚解决两个问题,由于惩罚,第二个参与者获得第一名,鲁道夫获得第二名。