Правила торговли
Задачу добавил: alef
Успешно сдано решений: 17
Не напрасно Василиса Премудрой называется. Пока старшие невестки Дарья да Наталья горевали, она правила торговли в сети «Коробейники» прочитала. Ох, обманул невесток распорядитель торговой залы. Оказывается, если покупки в одном магазине делать, то неважно, сколько товаров приобретается, и сколькими картами покупка оплачивается.
Одна только проблема – в разных магазинах разный товар в наличии есть, а расположены магазины далеко друг от друга. Так что успеть до сроку можно только в один магазин. Ваша задача – написать программу, определяющую для каждой из невесток магазин, после посещения которого у нее останется минимально возможное количество неизрасходованных средств на карте.
Формат входного файла input.txt
Каждая из первых трех строк содержит следующую информацию.
Первое целое число в строке Km (m = 1, 2, 3; 1 <= Km <=10) – количество карт, содержащихся в наборе, выданном одной из невесток. За ним идут Km целых чисел через пробел – номиналов подарочных карт, содержащихся в наборе (номинал карты выражен в рублях и может находиться в диапазоне от 1 до 10000 рублей).
Четвертая строка – целое число N (3 < N <= 100) – количество предметов в списке и через пробел целое число M (1 < M <= 10) – количество магазинов сети «Коробейники».
Каждая из следующих N строк состоит из наименования предмета Sj (строчными латинскими буквами, каждое наименование не длиннее 255 символов), через пробел – его цена в рублях Pj (j = 1, 2, …, N; 1 <= Pj <=100000, Pj – целое число), далее через пробел указано количество магазинов, в которых присутствует товар, и перечисляются номера магазинов, в которых товар присутствует.
Примечание. Количество товара каждого наименования в магазине считается неограниченным.
Формат выходного файла output.txt
Первая строка – номер магазина, который следует посетить первой невестке, и через пробел минимально возможный суммарный остаток средств на картах из первого набора
Вторая строка – номер магазина, который следует посетить второй невестке, и через пробел минимально возможный суммарный остаток средств на картах из второго набора
Третья строка – номер магазина, который следует посетить третьей невестке, и через пробел минимально возможный суммарный остаток средств на картах из третьего набора
Примечание. Если несколько магазинов одновременно удовлетворяют условию задачи, следует вывести меньший номер магазина.
Пример входного файла