1304: 停课危机

Memory Limit:128 MB Time Limit:1.000 S Judge Style:Text Compare Creator:
Submit:4 Solved:1

Description

2023年的冬季注定不太平,这是一个疫情高发的季节,感冒、支原体肺炎、新冠、甲流、乙流、麻疹、疟疾、肺结核、腮腺炎等传染病肆虐,令人防不胜防。目前的传染病共有D1D15)种,由1D编号。

湖南涉外经济学院共有N1N1000)名老师,部分抵抗力强的老师们没患任何传染病(比如一向身强体壮的彭院长、成天吃大补丸和海鲜的涛教授、每天不是打乒乓球就是游泳的富二代王凌风老师),但也有部分老师们也饱受传染病之苦(比如天天除了上课还要打杂和跑装修的累成狗的黄希贝老师、挑食这也不吃那也不吃还不运动导致抵抗力差的周孟娜老师),但是为了不被辞退,不少老师坚持带病上岗,甚至很多老师同时患了多种传染病。

这天,学校接到省教育厅通知,如果到校上班的老师,所患的传染病加起来超过K1KD)种,就可能导致传染病大爆发,学校就要停课。

给定所有的教师患病的情况,请你编程计算,要使到校上班的老师所患的传染病加起来不超过K种,学校最多允许多少名老师来上班?

不允许普通用户打印题目,请教师登录后使用。如有疑问请联系管理员!

Input

输入包含多组测试用例,每组测试用例占若干行,每组测试用例的第1行有三个用空格隔开的整数NDK,含义见问题描述,接下来的N行每行表示一名老师所患的传染病列表:第一个数di (0diD)表示该老师共患了di种传染病,紧接着的di个整数表示该教师所患的传染病的编号,相邻两数之间用空格隔开。

Output

对于每一组测试数据,仅输出一行,表示最多允许多少名老师来上班。

Sample Input Copy

6 3 2
0
1 1
1 2
1 3
2 2 1
2 2 1
5 5 1
2 1 2
2 1 3
2 1 4
2 1 5
2 2 3

Sample Output Copy

5
0