Time Limit:10000ms Memory Limit:65536KB

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


Author

Source

hust Monthly, June 2010