Сан Саныч был известным нумизматом. Когда он приезжал в другую страну, то
сразу находил какой-нибудь магазин для коллекционеров и приобретал там все
местные монеты, которых ещё не было в его коллекции.
Приехав в Японию и оказавшись в таком магазине, он сразу прикинул, какие
японские монеты ему интересны. Он уже собирался их приобрести, когда узнал,
что все монеты в этом магазине упакованы в прозрачные коробочки по несколько
штук и продаются только вместе. Причём все коробочки продаются по одной
и той же цене в 200 йен. Сан Саныч был готов купить и лишние монеты,
если в итоге каждая нужная монета обошлась бы ему не более чем в 100 йен.
Он стал рассматривать коробочки: нужные ему монеты присутствовали во многих
из них в разных сочетаниях. Сделать выбор оказалось весьма непросто.
Увидев замешательство покупателя, продавец вызвался помочь и попросил список
нужных ему монет. Сан Саныч перечислил монеты, но сказал, что купит набор
коробочек, только если его стоимость не будет превышать ценность покупки.
Чтобы подсчитать ценность покупки для Сан Саныча, нужно сложить по 100 йен
за каждую различную нужную ему монету. Продавец сказал, что подберёт подходящий
набор коробочек и даже уступит его за полцены при условии покупки всего набора.
Сан Саныч согласился, и, разумеется, ему пришлось купить самый большой набор
коробочек, стоимость которого с учётом скидки не превосходила его ценности.
При этом в наборе могли быть и совершенно лишние коробочки —
такие, которые можно исключить без уменьшения ценности набора. Но упускать
столь выгодное предложение было нельзя. Тем более что продавец был вежлив
и не стал включать в набор коробочки, в которых не было ни одной нужной
покупателю монеты.
Попробуйте определить, какие коробочки мог предложить Сан Санычу продавец.
Исходные данные
В первой строке записаны два целых числа: n — количество
разновидностей японских монет (1 ≤ n ≤ 100), k —
количество коробочек, имеющихся в магазине (1 ≤ k ≤ 50). В каждой
из следующих k строк описано по одной коробочке. Первым в строке указано
число ki — количество монет в коробочке
(1 ≤ ki ≤ 100), далее через пробел следует ровно
ki чисел, обозначающих японские монеты. Монеты пронумерованы
от 1 до n. Все монеты в коробочке различны.
В последней строке приведён список монет, интересующих Сан Саныча. Первым числом
в строке идёт количество монет в списке m (1 ≤ m ≤ 100).
Далее следует сам список: m чисел от 1 до n, разделённых пробелами.
Все монеты в списке различны.
Результат
В первой строке выведите количество коробочек, которые купил Сан Саныч.
В следующей строке через пробел выведите номера этих коробочек. Коробочки
пронумерованы от 1 до k в том порядке, в котором они приведены
во входных данных. Если вариантов ответа несколько, выведите любой.
Пример
исходные данные | результат |
---|
10 4
5 2 7 6 1 3
6 6 7 10 2 9 4
5 1 8 3 9 2
5 4 3 7 6 1
4 8 5 4 9
| 3
2 3 4
|
Автор задачи: подготовил Владимир Яковлев, особая благодарность Владиславу Исенбаеву
Источник задачи: Открытое личное первенство УрГУ 2009 (28 февраля 2009)