小坑坑的称号

Time Limit: 1000MS

Memory Limit: 131072KB

Description

小坑坑很喜欢玩CF---CROSS FIRE。CF里面有很多称号,例如玩挑战模式玩的很好会有挑战之王称号,玩爆破玩的很好会有爆破之王的称号等。小坑坑是只奇葩,在CF里建了个工会,可惜没人加入,于是他打算自己申请小号加入,于是他申请了很多的QQ号,可是CF有个规定,一个ID必须得有至少一个称号才能加入工会,于是小坑坑这只奇葩就天天换着号来玩CF。。。终于把所有的小号都加进去了,但是他又发现一个问题,所有的帐号都用一个密码实在不安全,各不一样又不好记(小坑坑申请了1000个QQ号。)。于是他。他决定按照称号来分配密码。一个称号分配一个密码。然后他又发现一个问题,有些小号获得了不止一个称号。比如ID为 CF1的小号获得了两个称号“挑战之王”与“爆破之王”,到底该怎么来改CF1的密码?小坑坑希望把密码都改好后使得拥有帐号最多的那个密码的帐号数目最少。然后他问你,帐号最多的那个密码的拥有的帐号数目最少是多少。

Input

一个整数(1 <= N <= 1000)表示小Q的帐号数,一个整数(1 <= M <= 500)表示称号总数。接下来N行,每行开始包括一个ID(长度<=15的英文字符和数字组成,每个ID都不一样)一个整数K,然后K个称号(长度<= 15的英文字符和数字组成,每个称号都不一样),以“0 0 ”结束输入。

Output

把每个帐号分配好密码后,拥有帐号最多的那个密码的帐号数目。

Sample Input

3 2
CF1 2 Killer Fire
CF2 1 Fire
CF3 1 Fire
5 4
CF4 3 Sorry CROSS ACM
CF5 2 TK Sorry
Asian 3 TK CROSS ACM
littleQ 2 Sorry CROSS
bigQ 2 TK CROSS
0 0

Sample Output

2
2

Hint

样例一有两种分配密码的方式:

第一种: CF1 CF2 CF3 都分配Fire称号的密码。

第二种: CF1 分配Killer 称号的密码, CF2 CF3分配Fire称号的密码。

显然第二种符合题意。拥有帐号最多的那个密码的帐号数目是2(CF2, CF3)。

Source

Missa_chen

提交代码