Moo University (moo.X)
Moo U's cafeteria has run out of hay and so must order pizzas for
the C (1 <= C <= 1,000) student cows attending Moo U. Conveniently, a
large pizza from the local pizzeria, Pizza Farm, serves exactly one
student.
Pizza Farm is willing to make a pizza for each student, but, due to
the size of the order, there are three constraints:
* Although Pizza Farm has long list of T (1 <= T <= 30)
toppings (all vegetarian), each of the pizzas must have exactly K (1 <= K <=
T) toppings
* No topping on a pizza may be duplicated (a pizza cannot have
onions and onions, for example).
* No two pizzas in the order can have the same set of toppings.
For example, if pizza 1 has onions, green peppers, pineapples,
and wheat grass, then it can be the only pizza with that exact
set of toppings, although pizza 2 might have onions, green
peppers, pineapples, and also olives.
For ordering purposes, the toppings are numbered 1..T.
The students at Moo U are very picky when it comes to their pizza
toppings. Some students might not like all of the toppings available.
A student will eat a pizza only if she likes every single one of the
toppings on that pizza. Your task is to determine the maximum number of students
that can be fed.
PROBLEM NAME: moo
INPUT FORMAT:
* Line 1: Three integers: C, T, and K.
* Lines 2..C+1: Each line of space-separated integers describes which
toppings one of the students likes. The first integer on a line
is the number of topping the student likes. The remaining
integers on the line are the toppings that the student likes.
SAMPLE INPUT:
3 2 1
2 2 1
1 1
1 2
INPUT DETAILS:
There are three students. Pizza Farm has two toppings and each pizza
must have exactly one topping. The first student likes both of the
toppings, the second student likes only the first topping, and the
third student likes only the second topping.
OUTPUT FORMAT:
* Line 1: A single integer, the maximum number of students that can be fed.
SAMPLE OUTPUT:
2
OUTPUT DETAILS:
There are only two pizzas that can be made: a pizza with topping 1 and a
pizza with topping 2. If the first pizza is given to the first
student (since she likes topping 1) and the second pizza to the third student
(since she likes topping 2), two students will be fed. There is no way to feed
all three, however.