Обзавод
Задачу добавил: alef
Успешно сдано решений: 38
Наутро позвал к себе царь невесток и сообщил им, что, рассмотрев их пожелания, составил список необходимых им в быту предметов, и дает им задание – приобрести эти предметы. Для чего приготовил он три набора подарочных карт сети магазинов «Коробейники», где все эти предметы продаются. Каждая невестка получает свою копию списка и набор карт и может покупать любые предметы из списка (разумеется, по одному, и не обязательно все). Однако для покупок можно использовать только подарочные карты. У подарочной карты особенность такая: если цена приобретенного товара меньше номинала карты, остаток карты использовать нельзя.
Самой хозяйственной обещал царь назвать ту, у которой меньше всего неизрасходованных средств на картах останется. Сумма номиналов карт в каждом наборе одна и та же.
Поблагодарили невестки царя, и скорее в магазин: сроку на покупки только сутки и дано.
А в магазине встретил их распорядитель залы торговой и сообщил, что для подарочных карт действует правило «одна карта – один предмет»: одну карту, по его словам, можно использовать для оплаты только одного предмета, а если ее номинала не хватает, можно доплатить, но только деньгами.
Пригорюнились невестки: денег тратить не велено. Взяли прайс-свитки у распорядителя да пошли думу думать: что же приобрести, чтобы хозяйственной прослыть.
Ваша задача – написать программу, которая поможет невесткам выбрать предметы таким образом, чтобы суммарный остаток средств на картах был наименьшим.
Формат входного файла input.txt
Каждая из первых трех строк содержит следующую информацию.
Первое целое число в строке Km (m = 1, 2, 3; 1 <= Km <=100) – количество карт, содержащихся в наборе, выданном одной из невесток. За ним идут Km целых чисел через пробел – номиналов подарочных карт, содержащихся в наборе (номинал карты выражен в рублях и может находиться в диапазоне от 1 до 100000 рублей).
Четвертая строка – целое число N (3 < N <= 100) – количество предметов в списке
Каждая из следующих N строк состоит из наименования предмета Sj (строчными латинскими буквами, каждое наименование не длиннее 255 символов) и – через пробел – его цены в рублях Pj (j = 1, 2, …, N; 1 <= Pj <=100000, Pj – целое число).
Примечание. Количество товара каждого наименования в магазине считается неограниченным.
Формат выходного файла output.txt
Первая строка – минимально возможный суммарный остаток средств на картах из первого набора
Вторая строка – минимально возможный суммарный остаток средств на картах из второго набора
Третья строка – минимально возможный суммарный остаток средств на картах из третьего набора
Пример входного файла
3 2000 100 400
5 100 100 100 1500 700
7
kofemolka 200
mikser 150
vodonagrevatel 3500
chainik 200
pylesos 1700
mikrovolnovka 1980
kofevarka 710
Пример выходного файла
320
1590