#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <queue>
//  by zrt
//  problem:la3268
//  无论你在什么时候开始，重要的是开始以后就不要停止。
using namespace std ;
typedef long long LL ;
const double eps(1e-10) ;
const int inf(0x3f3f3f3f) ;
int n,m;
int H[1600],X[1500000],P[1500000],flow[1500000],tot;
int hh[1600],xx[1500000],pp[1500000],floww[1500000];
inline void add(int x,int y,int z){
	P[++tot]=y;X[tot]=H[x];H[x]=tot;flow[tot]=z;
}
char s[2000];
int S,T;
int tott;
queue<int>q;
int d[1600];
bool bfs(){
	memset(d,0,sizeof d);
	d[S]=1;q.push(S);int k;
	while(!q.empty()){
		k=q.front();q.pop();
		for(int i=H[k];i;i=X[i]){
			if(flow[i]>0&&!d[P[i]]){
				d[P[i]]=d[k]+1;
				q.push(P[i]);
			}
		}
	}
	return d[T];
}
int dfs(int x,int a){
	if(x==T||a==0) return a;
	int f=a,tmp;
	for(int i=H[x];i;i=X[i]){
		if(flow[i]>0&&d[P[i]]==d[x]+1){
			tmp=dfs(P[i],min(flow[i],a));
			a-=tmp;
			flow[i]-=tmp;
			flow[i^1]+=tmp;
			if(!a) break;
		}
	}
	if(f==a) d[x]=-1;
	return f-a;
}
int Dinic(){
	int f(0);
	while(bfs()) f+=dfs(S,inf);
	return f;
}
bool judge(int x){
	tot=tott;
	memcpy(P,pp,sizeof P);
	memcpy(H,hh,sizeof H);
	memcpy(X,xx,sizeof X);
	memcpy(flow,floww,sizeof flow);
	for(int i=1000+m-1;i>=1000;i--){
		add(i,T,x);
		add(T,i,0);
	}
	if(Dinic()==n) return 1;
	else return 0;
}
int main(){
	#ifdef LOCAL
	freopen("in.txt","r",stdin) ;
	freopen("out.txt","w",stdout) ;
	#endif
	S=1599,T=1598;
	while(scanf("%d%d",&n,&m),n+m){
		memset(H,0,sizeof H);
		tot=1;
		int x;
		for(int i=0;i<n;i++){
			scanf("%*s");
			add(S,i,1);
			add(i,S,0);
			gets(s);
			for(int j=0;s[j];j++){
				if(isdigit(s[j])){
					sscanf(s+j,"%d",&x);
					add(i,x+1000,1);
					add(x+1000,i,0);
					while(isdigit(s[j])) j++;
					j--;
				}
				
			}
		}
		memcpy(hh,H,sizeof H);
		memcpy(xx,X,sizeof X);
		memcpy(floww,flow,sizeof flow);
		memcpy(pp,P,sizeof P);
		tott=tot;
		int l=0,r=n,M;
		while(l<r-1){
			M=(l+r)>>1;
			if(judge(M)) r=M;
			else l=M;
		}
		printf("%d\n",r);
	}
	
	return 0 ;
}