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)$$$的惩罚解决两个问题,由于惩罚,第二个参与者获得第一名,鲁道夫获得第二名。