ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Open Personal Contest 2009

About     Problems     Submit solution     Judge status     Standings
Contest is over

H. Numismatics for Fun

Time limit: 0.5 second
Memory limit: 64 MB
San Sanych was a famous numismatist. Every time he came to another country he would find a shop for collectors at once and buy there all local coins missing in his collection.
When he came to Japan and found such a shop, he figured which Japanese coins were interesting to him. He was going to buy them when he noticed that all the coins in that shop were packed in transparent boxes, several coins in one box, and one could buy whole boxes only. The price for all boxes was the same—200 yen. San Sanych was ready to buy some extra coins if eventually every coin that he needed would cost him no more than 100 yen. He started to examine the boxes. The required coins were present in many boxes in different combinations. It was not easy to make the choice.
Seeing the customer's confusion, the shopkeeper offered her help and asked which coins he wanted. San Sanych named the coins and added that he would buy several boxes if their total cost didn't exceed the value of the purchase. In order to determine the value of a purchase, San Sanych counts the number of different new coins in the purchase and multiplies the number by 100 yen. The shopkeeper said that she would select a suitable set of boxes and let San Sanych have it at half-price if he bought the whole set. Of course, in this case he might have to buy some redundant boxes—those that could be excluded without decreasing the value of the set. San Sanych couldn't miss the chance to get a discount and agreed to buy a set with the total cost, the discount taken into account, not exceeding its value. The shopkeeper was very kind and promised not to include into the set boxes that contained none of the required coins. Naturally, San Sanych left the shop with the largest set satisfying the above conditions.
Your task is to determine which boxes the shopkeeper included in the set.


In the first line there are two integers: the number n of kinds of Japanese coins in the shop (1 ≤ n ≤ 100) and the number k of boxes in the shop (1 ≤ k ≤ 50). The boxes are described in the following k lines. Each of these lines starts with the number ki of coins in a box (1 ≤ ki ≤ 100). Then there are exactly ki numbers denoting coins. The numbers are separated with a space. The coins are numbered from 1 to n. All coins in each box are different.
In the last line you are given the list of coins that San Sanych wants to buy. The first number in this line is the number m of coins in the list (1 ≤ m ≤ 100). Then there are m numbers from 1 to n separated with a space. All numbers in the list are different.


In the first line output the number of boxes San Sanych bought. In the next line, give the numbers of these boxes separated with a space. The boxes are numbered from 1 to k as they are given in the input. If there are several possible answers, output any of them.


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
2 3 4
Problem Author: prepared by Vladimir Yakovlev, special thanks to Vladislav Isenbaev
Problem Source: USU Open Personal Contest 2009 (February 28, 2009)
To submit the solution for this problem go to the Problem set: 1687. Numismatics for Fun