#include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <algorithm>

 #include <iostream>

 #include <vector>

 #include <queue>

 using namespace std;

 struct Edge{

     int from, to, cap, flow;

     Edge(int _from=, int _to=, int _cap=, int _flow=):

             from(_from), to(_to), cap(_cap), flow(_flow) {}

 }E[ + ];

 struct Dinic{

     static const int N =  + ;

     static const int M =  + ;

     static const int oo = 0x3f3f3f3f;

     int n, m, s, t;

     vector <Edge> edges;

     vector <int> G[N];

     int cur[N], dis[N];

     bool vi[N];

     void Clear(){

         for(int i = ; i <= n; ++ i) G[i].clear();

         edges.clear();

     }

     void Add(int from, int to, int cap, int flow){

         edges.push_back((Edge){from, to, cap, });

         edges.push_back((Edge){to, from, , });

         int m = edges.size();

         G[from].push_back(m-);

         G[to].push_back(m-);

     }

     bool bfs(){

         memset(vi, false, sizeof vi);

         dis[s] = ; vi[s] = true;

         queue <int> q;

         q.push(s);

         while(!q.empty()){

             int x = q.front(); q.pop();

             for(int i = ; i < G[x].size(); ++ i){

                 Edge &e = edges[G[x][i]];

                 if(!vi[e.to] && e.cap > e.flow){

                     vi[e.to] = true;

                     dis[e.to] = dis[x] + ;

                     q.push(e.to);

                 }

             }

         }

         return vi[t];

     }

     int dfs(int x, int a){

         if(x == t || a == ) return a;

         int flw = , f;

         for(int &i = cur[x]; i < G[x].size(); ++ i){

             Edge &e = edges[G[x][i]];

             if(dis[x] +  == dis[e.to] && (f = dfs(e.to, min(a, e.cap - e.flow))) > ){

                 e.flow += f; edges[G[x][i]^].flow -= f;

                 a -= f; flw += f;

                 if(a == ) break;

             }

         }

         return flw;

     }

     int MaxFlow(int s, int t){

         this->s = s; this->t = t;

         int flw = ;

         while(bfs()){

             memset(cur, , sizeof cur);

             flw += dfs(s, oo);

         }

         return flw;

     }

 }Net;

 int n, m;

 char buf[];

 int len, cnt = , x, np;

 int bj[ + ];

 int l, r, mid;

 bool check(int mv){

     Net.Clear();

     for(int i = ; i <= n; ++ i)

         Net.Add(, i, , );

     for(int i = ; i <= cnt; ++ i)

         Net.Add(E[i].from, E[i].to, , );

     for(int i = n + ; i <= n + m; ++ i)

         Net.Add(i, n + m + , mv, );

     return Net.MaxFlow(, n + m + ) == n;

 }

 void Solve(){

     int ans, l = ;

     while(l <= r){

         mid = l + (r - l) / ;

         if(check(mid)){

             ans = mid; r = mid - ;

         }

         else l = mid + ;

     }

     printf("%d\n", ans);

     return;

 }

 int main(){

     while(scanf("%d%d", &n, &m) && n && m){

         cnt = ;r = ;

         memset(bj, , sizeof bj);

         Net.n = n + m + ;

         for(int i = ; i <= n; ++ i){

             getchar();gets(buf);

             len = strlen(buf);

             for(int j = ; j < len;){

                 if(buf[j] < '' || buf[j] > ''){

                     j ++; continue;

                 }

                 while(buf[j] <= '' && buf[j] >= ''){

                     x = x *  + buf[j] - '';j ++;

                 }

                 ++ cnt;

                 E[cnt] = (Edge){i, x +  + n, , };

                 bj[E[cnt].to] ++;

                 r = max(bj[E[cnt].to], r);

                 x = ;

             }

         }

         Solve();

     }

     return ;

 }