Свадебный пир
Задачу добавил: alef
Успешно сдано решений: 2
Повелел царь устроить свадебный пир на весь мир. К свадебному пиру было решено заказать очень большие торты в известной сети магазинов «У Сергеича». И на это у царя подарочные карты припасены.
Поскольку необходимо накрыть три стола, царь выделил распорядителям пира на покупку три набора подарочных карт. Суммарный номинал карт в каждом наборе одинаков. По правилам этой сети магазинов в уплату за один товар может быть предъявлено любое количество карт. Если же стоимость покупки меньше номинала карты, остаток средств на ней «сгорает». Денег царь-батюшка распорядителям тратить не велел, а велел купить тортов так, чтобы остаток средств в каждом наборе карт оказался минимально возможным.
Формат входного файла input.txt
Каждая из первых трех строк содержит следующую информацию.
Первое целое число в строке Km (m = 1, 2, 3; 1 <= Km <=10) – количество карт, содержащихся в наборе, выданном распорядителям. За ним идут Km целых чисел через пробел – номиналов подарочных карт, содержащихся в наборе (номинал карты выражен в рублях и может находиться в диапазоне от 1 до 100000 рублей).
Четвертая строка – целое число N (1 < N <= 100) – количество тортов в прайс-листе
Каждая из следующих N строк состоит из наименования торта Sj (строчными латинскими буквами, каждое наименование не длиннее 255 символов) и – через пробел – его цены в рублях Pj (j = 1, 2, …, N; 1 <= Pj <=100000, Pj – целое число).
Примечание. Количество тортов каждого наименования в магазине считается неограниченным.
Формат выходного файла output.txt
Первая строка – минимально возможный суммарный остаток средств на картах из первого набора
Вторая строка – минимально возможный суммарный остаток средств на картах из второго набора
Третья строка – минимально возможный суммарный остаток средств на картах из третьего набора
Пример входного файла
10 1 2 3 4 5 6 7 8 9 10
1 8
12
tort 1
tortik 2
tort 4
tort 1
tort 2
tort 4
tort 11
tort 12
tort 14
tort 111
tort 211
tort 411
Пример выходного файла
0
4