MOOPIZZA - Moo University - Emergency Pizza Order

no tags 

Moo U's cafeteria has run out of hay and so must order pizzas for the C (1 <= C <= 1,000) calves attending Moo U. Conveniently, a large pizza from the local pizzeria, Pizza Farm, serves exactly one calf.

Pizza Farm is willing to make a pizza for each calf, but, due to the size of the order, has three constraints on the order:

* Although Pizza Farm has long list of T (1 <= T <= 30) vegetarian toppings, each of the pizzas must have exactly K (1 <= K <= T) toppings

* No topping on a pizza can 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 calves at Moo U are very picky when it comes to their pizza toppings. Some calves might not like all of the toppings available. A calf will eat a pizza only she likes every single one of the toppings on that pizza. Determine the maximum number of calves that can be fed.

Input

* Line 1: Three integers: C, T, and K. * Lines 2..C+1: Each line of space-separated integers describes which toppings one of the calves likes. The first integer on a line is the number of topping the calf likes. The remaining integers on the line are the toppings that the calf likes.

Output

* Line 1: A single integer, the maximum number of calves that can be fed.

Example

Input:

3 2 1
2 2 1
1 1
1 2

Input details:

There are three calves. Pizza Farm has two toppings and each pizza must have exactly one topping. The first calf likes both of the toppings, the second calf likes only the first topping, and the third calf likes only the second topping.

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 calf (since she likes topping 1) and the second pizza to the third calf (since she likes topping 2), two calves will be fed. There is no way to feed all three calves.


hide comments
Slobodan: 2009-04-14 11:11:12

Probably you should ask admins to do that for you.

Neal Wu: 2009-04-11 20:54:47

I have some stronger test cases, but unfortunately I can't upload them...

[Trichromatic] XilinX: 2009-03-09 13:26:00

Don't know the standard algorithm - but actually passed...

Last edit: 2009-04-11 20:47:12

Added by:Mir Wasi Ahmed
Date:2009-01-07
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:USACO 2004 March Green Division, Problemsetter - Hal Burch