Завершилось очередное соревнование по программированию. К Вам в руки попала таблица с финальными результатами этого соревнования. Для каждой команды в ней было указано количество задач, решенных данной командой, а также суммарное штрафное время данной команды по всем решенным ей задачам. Однако ни для одной команды в этой таблице не было указано ее финальное место.
Вам известны правила, по которым можно сравнить результаты двух заданных команд. Пусть команда a решила pa задач с суммарным штрафным временем ta, а команда b решила pb задач с суммарным штрафным временем tb. Тогда команда a займет более высокое итоговое место, чем команда b, если она решила больше задач на соревновании, либо она решила такое же количество задач, но с меньшим суммарным временем. Другими словами, команда a окажется выше команды b в финальной таблице результатов, если pa > pb, либо pa = pb и при этом ta < tb.
При этом считается, что команды, решившие одинаковое количество задач с одинаковым штрафным временем, делят между собой все соответствующие места. Более формально, пусть есть группа из x команд, которые решили одинаковое количество задач с одинаковым штрафным временем. Пусть также y команд выступили лучше команд из этой группы. Тогда все команды из группы разделят между собой y + 1, y + 2, ..., y + x места. Команды, результат которых хуже чем у команд из группы, получат свои места в итоговой таблице, начиная с y + x + 1 места.
Вашей задачей будет посчитать, какое количество команд из заданного списка разделило между собой k-ое место.
Примечание
Итоговая таблица для первого примера:
- 1-3 места — 4 решенных задачи, штрафное время равно 10
- 4 место — 3 решенных задачи, штрафное время равно 20
- 5-6 места — 2 решенные задачи, штрафное время равно 1
- 7 место — 1 решенная задача, штрафное время равно 10
По таблице видно, что второе место разделили команды, решившие 4 задачи со штрафным временем 10. Всего есть 3 такие команды.
Итоговая таблица для второго примера:
- 1 место — 5 решенных задач, штрафное время равно 3
- 2-5 места — 3 решенные задачи, штрафное время равно 1
По таблице видно, что четвертое место разделили команды, решившие 3 задачи со штрафным временем 1. Всего есть 4 такие команды.