C. Рудольф и очередное соревнование
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рудольф зарегистрировался на соревнование по спортивному программированию, которое пройдет по правилам 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)$$$, соответственно, благодаря штрафу второй участник получит первое место, а Рудольф второе.