時間制限:1000ミリ秒
メモリ制限:30000KB
問題
Moo大学は食堂のわらを切らしてしまったので、C(1 <= C <= 1,000)匹の牛達のために、地元のピザ屋Pizza Farmから、一匹あたりちょうど一個のピザを注文しなければならなくなった。
Pizza Farmは各々の牛に対してピザを作りたいと思っているが、注文の量が多いため、注文に次の3つの条件をつけた。
*Pizza FarmにはT(1 <= T <= 30)種類のトッピングがあるが、そのうちちょうどK(1 <= K <= T)種類をピザに載せなければならない。 *ひとつのピザに同じトッピングを2つ以上してはならない(たとえば、オニオンとオニオンというトッピングはできない)。 *どの2つのピザもおなじトッピングの組み合わせを持ってはいけない。
Moo大学の牛達はピザのトッピングについてうるさい。牛によっては全てのトッピングが好きとは限らない。
牛達は、自分の好きなトッピングだけがのっているピザだけを食べる。ピザを食べることができる牛の数を最大化せよ。
入力
1行: スペースで区切られた3つの整数 C, T, K
2~C+1行: スペースで区切られた i番目の牛の好きなトッピングに関する情報。一つ目の数字は好きなトッピングの個数。残りの数字は好きなトッピングの番号.
出力
1行: 1つの整数 ピザを食べることができる牛の最大数。
入力の例
3 2 1 2 2 1 1 1 1 2
出力の例
2
ヒント
トッピングの種類は2つで、ピザに載せることができるトッピングの個数は1つである。トッピング1がのってるピザと、トッピング2がのってるピザを注文すれば2匹の牛がピザを食べることができる。3匹が食べることができる組み合わせは存在しない。
出典
USACO 2004 March Green