HUST Monthly 2010.06.13

From: 2010-06-13 12:00:00 To: 2010-06-13 17:00:00 Now: 2017-09-20 01:02:07 Status: Public

C - Emergency relief

Time Limit: 10s Memory Limit: 128MB

Submissions: 284 Solved: 72
Description
Before referring to this problem, please stand in silent tribute for the victims of Qinghai In April, 14th, 2010, two earthquakes take place in Yusu of Qinghai province in the morning, the highest earthquake e maqnitude reaches 7.1. Till 17:00 in 23th, it has caused 2192 death, 78 missing, 12135 injured. According to reports, the disaster area is now in urgent need of tents, bedclothes, living materials and cold protection materials etc. . HUST urgently calls these relief supplies to convey to the disaster area. Unfortunately, because of the limits of traffic conditions, there is only a part of kinds of relief supplies reached the victims. Considering the matter in any way urgent, HUST needs your help, it’s up to you to decide what kind of relief supplies will be conveyed so that it can help as many as victims. For a victim, he/she can be helped only if all the relief supplies he/she need have been reached. Assuming that every kind of material is abundant.
Input
50 groups of data in total, for every group of data, three integers , n m k, in the first row: n (0 < n <= 16) shows the total kinds of relief supplies, which is marked 1 to n; m (0 < m <= n) indicates the maximum possible kinds of relief supplies that can be conveyed; k (0 < k <= 100000) expresses the number of victims. The followed k lines are every victim’s needed relief supplies, whose form is p a1 a2 … ap, among them, p is the number of kinds of the relief supplies, ai is the id of relief supply, and 1 <= ai <= n, in addition, ai will not be repeated.
Output
For every group of data, please output the maximum number of victims who can be helped
Sample Input
1 1 2
1 1
1 1
3 2 7
2 1 3
1 1
1 2
3 1 2 3
1 2
1 1
2 1 2
Sample Output
2
5
Hint
Source
Hust Monthly 10.06.13/Xuehui SONG