• Source 
    1. #include <cstdio>
    2. #include <cstring>
    3. #include <algorithm>
    4. #include <cctype>
    5. #include <queue>
    6. //  by zrt
    7. //  problem:la3268
    8. //  无论你在什么时候开始，重要的是开始以后就不要停止。
    9. using namespace std ;
    10. typedef long long LL ;
    11. const double eps(1e-10) ;
    12. const int inf(0x3f3f3f3f) ;
    13. int n,m;
    14. int H[1600],X[1500000],P[1500000],flow[1500000],tot;
    15. int hh[1600],xx[1500000],pp[1500000],floww[1500000];
    16. inline void add(int x,int y,int z){
    17. 	P[++tot]=y;X[tot]=H[x];H[x]=tot;flow[tot]=z;
    18. }
    19. char s[2000];
    20. int S,T;
    21. int tott;
    22. queue<int>q;
    23. int d[1600];
    24. bool bfs(){
    25. 	memset(d,0,sizeof d);
    26. 	d[S]=1;q.push(S);int k;
    27. 	while(!q.empty()){
    28. 		k=q.front();q.pop();
    29. 		for(int i=H[k];i;i=X[i]){
    30. 			if(flow[i]>0&&!d[P[i]]){
    31. 				d[P[i]]=d[k]+1;
    32. 				q.push(P[i]);
    33. 			}
    34. 		}
    35. 	}
    36. 	return d[T];
    37. }
    38. int dfs(int x,int a){
    39. 	if(x==T||a==0) return a;
    40. 	int f=a,tmp;
    41. 	for(int i=H[x];i;i=X[i]){
    42. 		if(flow[i]>0&&d[P[i]]==d[x]+1){
    43. 			tmp=dfs(P[i],min(flow[i],a));
    44. 			a-=tmp;
    45. 			flow[i]-=tmp;
    46. 			flow[i^1]+=tmp;
    47. 			if(!a) break;
    48. 		}
    49. 	}
    50. 	if(f==a) d[x]=-1;
    51. 	return f-a;
    52. }
    53. int Dinic(){
    54. 	int f(0);
    55. 	while(bfs()) f+=dfs(S,inf);
    56. 	return f;
    57. }
    58. bool judge(int x){
    59. 	tot=tott;
    60. 	memcpy(P,pp,sizeof P);
    61. 	memcpy(H,hh,sizeof H);
    62. 	memcpy(X,xx,sizeof X);
    63. 	memcpy(flow,floww,sizeof flow);
    64. 	for(int i=1000+m-1;i>=1000;i--){
    65. 		add(i,T,x);
    66. 		add(T,i,0);
    67. 	}
    68. 	if(Dinic()==n) return 1;
    69. 	else return 0;
    70. }
    71. int main(){
    72. 	#ifdef LOCAL
    73. 	freopen("in.txt","r",stdin) ;
    74. 	freopen("out.txt","w",stdout) ;
    75. 	#endif
    76. 	S=1599,T=1598;
    77. 	while(scanf("%d%d",&n,&m),n+m){
    78. 		memset(H,0,sizeof H);
    79. 		tot=1;
    80. 		int x;
    81. 		for(int i=0;i<n;i++){
    82. 			scanf("%*s");
    83. 			add(S,i,1);
    84. 			add(i,S,0);
    85. 			gets(s);
    86. 			for(int j=0;s[j];j++){
    87. 				if(isdigit(s[j])){
    88. 					sscanf(s+j,"%d",&x);
    89. 					add(i,x+1000,1);
    90. 					add(x+1000,i,0);
    91. 					while(isdigit(s[j])) j++;
    92. 					j--;
    93. 				}
    94.  
    95. 			}
    96. 		}
    97. 		memcpy(hh,H,sizeof H);
    98. 		memcpy(xx,X,sizeof X);
    99. 		memcpy(floww,flow,sizeof flow);
    100. 		memcpy(pp,P,sizeof P);
    101. 		tott=tot;
    102. 		int l=0,r=n,M;
    103. 		while(l<r-1){
    104. 			M=(l+r)>>1;
    105. 			if(judge(M)) r=M;
    106. 			else l=M;
    107. 		}
    108. 		printf("%d\n",r);
    109. 	}
    110.  
    111. 	return 0 ;
    112. }
    113.