Codeforces Round 113 (Div. 2) |
---|
Закончено |
Завершилось очередное соревнование по программированию. К Вам в руки попала таблица с финальными результатами этого соревнования. Для каждой команды в ней было указано количество задач, решенных данной командой, а также суммарное штрафное время данной команды по всем решенным ей задачам. Однако ни для одной команды в этой таблице не было указано ее финальное место.
Вам известны правила, по которым можно сравнить результаты двух заданных команд. Пусть команда 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-ое место.
В первой строке заданы два целых числа n и k (1 ≤ k ≤ n ≤ 50). Далее в n строках следует описание команд: i-ая строка содержит два целых числа pi и ti (1 ≤ pi, ti ≤ 50) — количество решенных задач и суммарное штрафное время i-ой команды, соответственно. Все числа в строках разделены пробелами.
В единственной строке выведите искомое количество команд, занявших k-ое место в итоговой таблице результатов.
7 2
4 10
4 10
4 10
3 20
2 1
2 1
1 10
3
5 4
3 1
3 1
5 3
3 1
3 1
4
Итоговая таблица для первого примера:
По таблице видно, что второе место разделили команды, решившие 4 задачи со штрафным временем 10. Всего есть 3 такие команды.
Итоговая таблица для второго примера:
По таблице видно, что четвертое место разделили команды, решившие 3 задачи со штрафным временем 1. Всего есть 4 такие команды.
Название |
---|