Рудольф зарегистрировался на соревнование по спортивному программированию, которое пройдет по правилам 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\) штрафных минут.
Рудольфу стало интересно какое место он займет на соревановании, если каждый участник будет решать задачи в оптимальном порядке исходя из предсказаний искусственного интеллекта. Будем считать, что при равенстве баллов и штрафных минут Рудольф займет наилучшее место.
Выходные данные
Для каждого набора входных данных выведите целое число — место Рудольфа в таблице результатов, если все участники будут решать задачи в оптимальном порядке.
Примечание
В первом примере Рудольф наберет \(2\) балла и \(50\) штрафных минут. Второй участник решит только одну задачу и наберет \(1\) балл и \(90\) штрафных минут. И третий участник успеет решить все \(3\) задачи и наберет \(3\) балла и \(240\) штрафных минут. Таким образом Рудольф займет второе место.
Во втором примере оба наберут \(1\) балл и \(30\) штрафных минут. При равенстве баллов Рудольфу достается лучшая позиция, поэтому он займет первое место.
В третьем примере Рудольф единственный участник, поэтому он займет первое место.
В четвёртом примере все участники могут решить две задачи со штрафом в \(25 = 8 + (8 + 9)\), \(24 = 7 + (7 + 10)\) и \(26 = 8 + (8 + 10)\), соответственно, благодаря штрафу второй участник получит первое место, а Рудольф второе.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
2
1
1
2
1
|