这中类型的题做过两道了，所以一见题就知道思路了。不过这题的输入比较恶心，还好能应付。
本来不想做这题的，但是看到数据也还大1500个点，想用链表试试，先敲了个二维数组，等待TLE的过程中1Y了....
何其蛋疼！1500ms 不算快...
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<map>
#define CC(a) memset(a,0,sizeof(a))
#define FF(i,a) for( int i=0;i<a;i++ )
#define MN 1555
#define ME 555555
template<class T> void inline checkmin( T &a,T b ){ if(a==-1||a>b)a=b; }
using namespace std;struct Edge{int v,c,next;
}E[ME];
int N,NE,M,s,t,CAN;
int head[MN],gap[MN],pre[ME],dis[MN],cur[MN];
int maze[MN][MN],cap[MN][MN];void setG()
{CC(cap);map<string,int>map;string str;int num;char c;s=0;t=N+M+1;FF( i,N ){cin>>str;map[str]=M+i+1;num=-1;// people:[M+1,M+N] list:[1,M]while( scanf("%c",&c) ){if( c==' '||c=='\n' ){if( num==-1 ) continue;else cap[num+1][map[str]]++;if( c=='\n' ) break;num=-1;}else{if( num==-1 ) num=c-'0';else num=num*10+c-'0';}}}for( int i=M+1;i<=M+N;i++ )cap[i][t]=1;
}void initG( int mid )
{for( int i=0;i<=t;i++ )for( int j=0;j<=t;j++ )maze[i][j]=cap[i][j];for( int i=1;i<=M;i++ )maze[s][i]=mid;
}bool sap()
{CC(cur);CC(gap);CC(pre);CC(dis);int u=pre[s]=s,maxflow=0,aug=-1;gap[0]=t+1;while( dis[s]<=t ){
loop:for( int v=cur[u];v<=t;v++ )if( maze[u][v]&&dis[u]==dis[v]+1 ){pre[v]=u;cur[u]=v;checkmin(aug,maze[u][v]);u=v;if( v==t ){maxflow+=aug;for( u=pre[u];v!=s;v=u,u=pre[u] ){maze[u][v]-=aug;maze[v][u]+=aug;}aug=-1;}goto loop;}int mind=t;for( int v=0;v<=t;v++ )if( maze[u][v]&&mind>dis[v] ){cur[u]=v;mind=dis[v];}if( --gap[dis[u]]==0 )break;gap[dis[u]=mind+1]++;u=pre[u];}if( maxflow==N ) return true;else return false;
}int main()
{while( scanf("%d%d",&N,&M)!=EOF ){if( N==0&&M==0 )break;setG();int l=1,r=N,m;while( (m=(l+r)/2)&&l<r ){initG(m);if( sap() ) r=m;else l=m+1;}printf( "%d\n",m );}return 0;
}