Финал ACM ICPC

Ежегодно в Санкт-Петербурге, Барнауле и некоторых городах ближнего зарубежья проходят соревнования по программированию. Эти соревнования проходят в рамках студенческого чемпионата мира по программированию, организованного одной из самых авторитетных ассоциаций ACM (Association for Computing Machinery). На этих соревнованиях проходит отбор команд с Северо-Восточного Европейского Региона NEERC (North-Eastern European Regional Contest).

Ежегодно перед организаторами соревнований встает проблема определения команд, которые будут приглашены к участию в финале чемпионата мира по программированию. По новым правилам в финал проходят не более N команд, представляющих NEERC. Кроме этого, от одного университета не могут проходить более K команд. При этом из всех таких множеств выбирается то, в котором сумма мест, занятых этими командами в полуфинальных соревнованиях минимально возможная.

Ваша задача по итоговому протоколу полуфинальных соревнований и числам N и K определить, какие команды будут приглашены к участию в финале чемпионата мира.

Входные данные

В первой строке входного файла INPUT.TXT находится три натуральных числа: P – количество команд, принявших участие в полуфинале, N и K (N, K ≤ P ≤ 10⁵).

В следующих P строках, по одному в строке перечислены названия университетов, команды которых заняли соответствующие места. Название университета содержит строчные и прописные английские буквы и пробелы. Длина названия университета не превышает 30 символов. В следующей строке перечислены номера команд соответствующих университетов. Таким образом, если название университета записано в i-ой строке (2 ≤ i ≤ P+1), то эта команда заняла i-1 место на полуфинале и имеет номер, записанный на i-1 месте в P+2 строке.

Выходные данные

В выходной файл OUTPUT.TXT выведите названия команд, приглашенных к участию в финале чемпионата мира по программированию, упорядоченных по месту, занятому на полуфинале. В качестве названия команды выведите название университета и через пробел «#ID», где ID – номер команды.

Пример

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]