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.txtoutput.txt
2 2 10 1 1 1 5 1 2 6 5 1 2
Пояснение к примеру: в данном примере выручка гнома составит 6-1=5 золотых монет.


Источник: Petrozavodsk Winter 2003. SaratovSU #3 Training Contest, Wednesday, February 05

Обсудить       Отправить решение



Версия для печати