问题描述

$\text{Moo U}$ 的自助餐厅已经用完了干草，因此必须为 $C$（$1 \leq C \leq 1,\!000$）头参加 $\text{Moo U}$ 的小牛订购披萨。幸运的是，当地的披萨店 $\text{Pizza Farm}$ 愿意为每头小牛制作一个披萨，但由于订单量大，有以下三个约束条件：

1. 披萨配料数量：每个披萨必须恰好有 $K$（$1 \leq K \leq T$）种配料，$T$（$1 \leq T \leq 30$）是配料总数。
2. 配料唯一性：一个披萨上不能有重复的配料（例如，不能有两个洋葱）。
3. 配料组合唯一性：订单中不能有两个披萨有完全相同的配料组合。例如，如果一个披萨有洋葱、青椒、菠萝和小麦草，那么它必须是唯一具有这种精确配料组合的披萨，尽管另一个披萨可能有洋葱、青椒、菠萝和橄榄。

对于订购目的，配料编号为 $1..T$。

$\text{Moo U}$ 的小牛对披萨配料非常挑剔。有些小牛可能不喜欢所有可用的配料。

一头小牛只会吃她喜欢该披萨上的所有配料的披萨。确定可以喂饱的最大小牛数量。

输入

• 第 $1$ 行：三个整数 $C$、$T$ 和 $K$。
• 第 $2$ 行到第 $C+1$ 行：每行用空格分隔的整数描述一头小牛喜欢的配料。每行的第一个整数是小牛喜欢的配料数量，其余整数是小牛喜欢的配料。

输出

• 第 $1$ 行：一个整数，表示可以喂饱的最大小牛数量。

示例输入 $1$

3 2 1
2 2 1
1 1
1 2

示例输出 $1$

2

提示

示例输入：有三头小牛。$\text{Pizza Farm}$ 有两种配料，每个披萨必须恰好有一种配料。第一头小牛喜欢两种配料，第二头小牛只喜欢第一种配料，第三头小牛只喜欢第二种配料。

示例输出：只能制作两种披萨：一种配料 $1$ 的披萨和一种配料 $2$ 的披萨。如果第一种披萨给第一头小牛（因为她喜欢配料 $1$），第二种披萨给第三头小牛（因为她喜欢配料 $2$），那么可以喂饱两头小牛。

没有办法喂饱所有三头小牛。

来源

$\text{USACO 2004 March Green}$