1371 - Emergency relief
Time Limit : 10 Second
Memory Limit : 128 MB
Submission: 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