0186. Жадный гном
Имя входного файла: | input.txt |
Имя выходного файла: | output.txt |
Ограничение по времени: | 250 ms |
Ограничение по памяти: | 16 megabytes |
У жадного гнома скоро день рождение. У него есть книга "О дешевой пище" в которой содержится N (1 ≤ N ≤ 21) рецептов разных блюд. Чтобы приготовить блюдо номер k (для всех k=1…N) он должен затратить Ak золотых монет. У него есть M друзей (1 ≤ M ≤ 21). Каждый друг представил список тех угощений, которые обязательно должны быть на столе, чтобы он пришел. Известно, какой стоимости будет подарок каждого друга. Перед жадным гномом встала следующая непростая задача: какие блюда надо приготовить, чтобы выручка со дня рождения (сумма стоимостей подарков за вычетом денег, потраченных на готовку) была наибольшая. Так как гном не только жадный, но и ленивый, то если существует несколько таких наборов блюд, он хочет узнать набор с наименьшим количеством блюд. Гном уже понял, что готовить два одинаковых блюда смысла нет, то есть все блюда в наборе должны быть разные. Если решений несколько - выдайте любое из них.
Формат входного файла
В первой строке записаны два числа N и M. Далее идет строка, содержащая последовательность из N чисел A1, A2,…,AN - затраты на готовку блюд (1 ≤ Ak ≤ 10000, для всех k=1…N). Далее следует M строк, каждая из которых описывает гостя. Первое число S (1 ≤ S ≤ N) в описании - количество блюд, которые данный друг хочет видеть на столе. Далее следует S чисел - список номеров требуемых блюд. Все числа в списке различные, не большие N. Последнее число G (1 ≤ G ≤ 10000) в строке - стоимость подарка данного друга. Числа во всех строках входного файла разделяются пробелами. Во входном файле все числа натуральные.
Формат выходного файла
В первую строку выведите наибольшую возможную выручку гнома. Во вторую строку выведите число Q - количество блюд в оптимальном меню. В третью выдайте Q чисел - последовательность номеров блюд в найденном меню. Номера блюд выдавайте в произвольном порядке. Если любой вариант меню не дает положительной прибыли, то выведите 0 в первых двух строках.
Пример:
input.txt | output.txt |
---|---|
2 2 10 1 1 1 5 1 2 6 | 5 1 2 |
Источник: Petrozavodsk Winter 2003. SaratovSU #3 Training Contest, Wednesday, February 05
Обсудить Отправить решение
Версия для печати