Спортивное программирование

Подскажите максимально быстрый алгоритм , с помощью которого можно решить эту задачу.


Текст задачи:У жадного гнома скоро день рождение. У него есть книга «О дешевой пище» в которой содержится N (1 <= N <= 100) рецептов разных блюд. Чтобы приготовить блюдо номер k (для всех k = 1 .. . N) он должен затратить Ak золотых монет. У него есть M друзей (1 <= M <= 100). Каждый друг представил список тех угощений, которые обязательно должны быть на столе, чтобы он пришел. Известно, какой стоимости будет подарок каждого друга. Перед жадным гномом встала следующая непростая задача: какие блюда надо приготовить, чтобы выручка со дня рождения (сумма стоимостей подарков за вычетом денег, потраченных на готовку) была наибольшая. Так как гном не просто жадный, а очень жадный, то если существует несколько таких наборов блюд, он хочет узнать набор, при котором он получает наибольшее количество подарков. Гном уже понял, что готовить два одинаковых блюда смысла нет, то есть все блюда в наборе должны быть разные. Если решений несколько — выдайте любое из них.
Формат ввода:
В первой строке записаны два числа 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 в первых двух строках.
Пример ввода:
2 2
10 1
1 1 5
1 2 6

Пример вывода:
5
1
2

0