时间限制: 

1000ms 

内存限制: 

65536kB

描述

百度百科有一支神奇的队伍，他们叫自己“百科蝌蚪团”。为了更好的让蝌蚪团的成员们安排工作，百度百科的运营团队定出了一个24小时制的时间表。例如：

1.    每个蝌蚪团成员工作时长相同；

2.    必须安排蝌蚪团成员在他们方便的时间段工作；

3.    蝌蚪团成员安排时间最小安排时间节点（开始工作或停止工作）为半小时，比如04：00或04：30，而不是04：15；

4.    蝌蚪团成员一天在百度百科工作的时间是有上限的，他们会根据自己的情况给出上限。

5.    在特定时间段内必须有一定数量的蝌蚪团成员工作，以保证百度百科不断的进步

请帮运营团队计算一下，能保持24小时稳定在岗的蝌蚪团最少成员的数量。如果有2个蝌蚪团成员工作结束，同时另2个蝌蚪团成员开始工作，这段时间都算有2各成员稳定在岗。

输入

输入有多组，每组测试数据以一个整数N开头（1 ≤ N ≤ 50），表示蝌蚪团的成员数。紧接着，我们会有N个数据块，每一个数据块对应了一名蝌蚪团成员的日程情况。

每个数据块以两个整数开始，分别为K（1 ≤ K ≤ 50）和M（1 ≤ M ≤ 1440），用空格隔开。K表示这个数据块对应蝌蚪团成员方便的时间段的数量，M表示这个成员愿意每天在百度百科工作的最长分钟数。接下去的K行中，每行包括两个时间，分别表示成“HH：MM”的格式，以空格分隔，分别对应了该蝌蚪团成员一个方便的时间段的开始时间、结束时间；例如09：00 10：00表明他在早上九点到十点的时间段是方便的，可以在百度百科工作。如果两个时间相同，则说明这个他全天都是方便的。

最后一组数据的N为0，表示输入结束。

输出

对于每组数据，输出为一个整数，占一行。表示能保持24小时稳定在岗的蝌蚪团最少成员的数量。

样例输入

51 72018:00 12:001 108000:00 23:001 108000:00 20:001 105006:00 00:001 36018:00 00:0031 54000:00 00:003 48008:00 10:0009:00 12:0013:00 19:001 42017:00 00:0031 144000:00 00:001 72000:00 12:151 72012:05 00:150

样例输出

211

#include
    
     #include
     
      #include
      
       #define maxn 102int d[maxn],g[maxn][maxn],f[maxn][maxn],pre[maxn],map[maxn][maxn],sum[maxn],current[maxn];int n,m,num,mm;struct node{int x,y;}seg[1000],time[1000];#define oo 0xfffffffint cmp(const void *a,const void *b){struct node *va=(struct node*)a;struct node *vb=(struct node*)b;return va->x-vb->x;}void rev_bfs(int t){int queue[maxn],flag[maxn];int head,tail,i;memset(sum,0,sizeof(sum));for (i=0;i<=n+49;i++){d[i]=n+49;sum[n+49]++;}sum[n+49]--;sum[0]++;d[t]=0;queue[1]=t;flag[t]=1;head=1;tail=1;memset(flag,0,sizeof(flag));while (head<=tail){for (i=0;i<=n+49;i++)if (flag[i]==0&&g[i][queue[head]]>0){queue[++tail]=i;d[i]=d[queue[head]]+1;sum[n+49]--;sum[d[i]]++;flag[i]=1;}head++;}}void augment(int s,int t){int i,min;min=oo;for (i=t;i!=s;i=pre[i])if (g[pre[i]][i]
       
        0&&d[v]
        
         0&&d[u]==d[v]+1)break;if (v<=n+49){current[u]=v;pre[v]=u;u=v;if (u==t){augment(s,t);u=s;}}else if (retreat(&u,s)==0) return;}}void init(){int i,j,a,b,c,d,min,t,k,ans,max,st,en,temp;while (scanf("%d",&n)!=EOF&&n){memset(map,0,sizeof(map));;for (i=1;i<=n;i++){scanf("%d%d",&m,&t);map[48][i+48]=t/30;num=0;mm=0;for (j=1;j<=m;j++){scanf("%d:%d %d:%d",&a,&b,&c,&d);if (a==c&&b==d){for (k=0;k<48;k++)map[i+48][k]=1;continue;}if (c==0&&d==0){num++;seg[num].x=a*60+b;seg[num].y=1440;}else if (a*60+b>c*60+d){num++;seg[num].x=a*60+b;seg[num].y=1440;num++;seg[num].x=0;seg[num].y=c*60+d;}else{num++;seg[num].x=a*60+b;seg[num].y=c*60+d;}}if (num==0) continue;qsort(seg+1,num,sizeof(seg[1]),cmp);st=seg[1].x;en=seg[1].y;seg[num+1].x=1500;seg[num+1].y=1600;for (j=2;j<=num+1;j++){a=seg[j].x;b=seg[j].y;if (st<=a&&a<=en&&en
         
          en){mm++;time[mm].x=st;time[mm].y=en;st=a;en=b;}}for (j=1;j<=mm;j++){a=time[j].x/60;b=time[j].x-60*a;c=time[j].y/60;d=time[j].y-60*c;if (a==c){if (b==0&&d>=30)map[i+48][a*2]=1;}else{if (b>0&&b<=30) b=30;if (b>30) {a++;b=0;}if (d<30) d=0;if (d>30) d=30;while (a!=c||b!=d){map[i+48][a*2+b/30]=1;b+=30;if (b==60){a++;b=0;}}}}}max=oo;for (j=0;j<48;j++){temp=0;for (k=49;k
          
           0) temp++;if (temp
           
            ans) ans=min;}printf("%d\n",ans); } } int main() {//freopen("a.txt","r",stdin);//freopen("b.txt","w",stdout);init();return 0; }