Олимпиадный тренинг

Задача . Финал


Задача

Темы: Словари
Ежегодно в Санкт-Петербурге, Барнауле и некоторых городах ближнего зарубежья проходят соревнования по программированию. Эти соревнования проходят в рамках студенческого чемпионата мира по программированию, организованного одной из самых авторитетных ассоциаций АСМ (Association for Computing Machinery). На этих соревнованиях проходит отбор команд с Северо-Восточного Европейского Региона NЕЕRС (North-Eastern European Regional Contest). Ежегодно перед организаторами соревнований встает проблема определения команд, которые будут приглашены к участию в финале чемпионата мира по программированию. По новым правилам в финал проходят не более N команд, представляющих NEERC. Кроме этого, от одного вуза не может проходить более чем k команд. При этот из всех таких множеств выбирается то, в котором сумма мест занятых этими командами в полуфинальных соревнованиях минимальная возможная. Ваша задача по итоговому протоколу полуфинальных соревнований и числам N и k определить, какие команды будут приглашены к участию в финале чемпионата мира.
 
Входные данные
В первой сроке входного файла находится три натуральных числа Р (1 ≤ P ≤ 100000) — количество команд, принявших участие в полуфинале, N (1 ≤ N ≤ P ) и k (1 ≤ k ≤ P ) . В следующих P строках, по одному в строке перечислены названия университетов, команды которых заняли соответствующие места. Название университета содержит строчные и прописные латинские буквы и пробелы. Длина названия университета не превышает 30 символов. В следующей строке перечислены номера команд соответствующих университетов. Таким образам если название университета записано в i -той строке (2 ≤ i ≤ P + 1) , то эта команда заняла i - 1 место на полуфинале и имеет номер, записанный на i - 1 месте в P + 2 строке.
 
Выходные данные
В выходной файл выведите названия команд, приглашенных к участию в финале чемпионата мира по программированию, упорядоченных по месту, занятому на полуфинале. В качестве названия команды выведите название университета и через пробел #номер команды.
 
Пример
Входные данные Выходные данные
1
9 5 2
Fantasy University
Crazy University
Fantasy University
Fantasy University
Very Good U
Good U
Very Good U
Crazy University
Good U
1 1 2 3 2 1 1 2 2
Fantasy University #1
Crazy University #1
Fantasy University #2
Very Good U #2
Good U #1



time 3000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w6426
Python100
Комментарий учителя