← К соревнованиям

Олимпиада школьников "Шаг в будущее"

Задача 6

Сложность: 37%

В ходе работы над оптимизацией компилятора для процессора из предыдущей задачи в фирме Хардсофт задумались об автоматическом выборе подпрограмм, которые станут инлайн- подпрограммами. Инлайн-подпрограммы - это такой способ сборки машинного кода, при котором тело подпрограммы во время компиляции подставляется непосредственно в место её вызова, и оно становится частью вызывающего кода. Таким образом, исключаются накладные расходы на вызов и завершение подпрограмм во время работы.

Инженеры фирмы Хардсофт считают, что инлайн-подпрограммами надо делать те, которые вызываются чаще всего. Однако вставка кода больших подпрограмм в места их вызова приведёт к резкому увеличению памяти, потребляемой программами, а для фирмы важна возможность лёгкой адаптации своего решения к промышленным устройствам, в которых значительную роль играет экономическая составляющая: в частности, необходимый для работы объём памяти должен быть минимальным.

Разработчики создали специальный анализатор, который определяет среднее количество запуска подпрограмм и размер каждой из них. Требуется определить, какие из подпрограмм можно встроить в инлайн-режиме, для увеличения быстродействия и в пределах доступной памяти.

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

В первой строке через пробел указаны натуральные числа NN, MM и XX. NN и MM не превышают 100 и являются количеством подпрограмм и количеством цепочек вызова, а XX не превышает 10610^6 и является количеством памяти (в килобайтах), доступным для размещения инлайн- подпрограмм. Далее идёт NN строк, где через пробел перечислены имена подпрограмм (из латинских слов длиной до 20 символов) и их размер в килобайтах (натуральное число от 1 до 1000). Далее - MM строк с описанием выявленных цепочек вызова: в них записаны имена подпрограмм через пробел, после которых также через пробел указано ожидаемое количество срабатываний этой цепочки за время работы программы (целое число от 1 до 1000).

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

В первой строке - количество подпрограмм, которые можно пометить инлайновыми, в последующих строках - имена этих подпрограмм в том порядке, в котором они были указаны во входных данных.

Требуется выбрать подпрограммы так, чтобы количество вызовов инлайн-подпрограмм за время работы программы было максимальным.

STDINSTDOUT
3 3 100
A 50
B 70
C 40 
A 1
A B 4
B C 6
2
A
C
3 3 100
A 50
B 70
C 40 
A 1
A C 3
B 10
1
B