Description

小西有一条很长的彩带，彩带上挂着各式各样的彩珠。已知彩珠有N个，分为K种。简单的说，可以将彩带考虑为x轴，每一个彩珠有一个对应的坐标(即位置)。某些坐标上可以没有彩珠，但多个彩珠也可以出现在同一个位置上。 小布生日快到了，于是小西打算剪一段彩带送给小布。为了让礼物彩带足够漂亮，小西希望这一段彩带中能包含所有种类的彩珠。同时，为了方便，小西希望这段彩带尽可能短，你能帮助小西计算这个最短的长度么？彩带的长度即为彩带开始位置到结束位置的位置差。

Input

第一行包含两个整数N, K，分别表示彩珠的总数以及种类数。接下来K行，每行第一个数为Ti，表示第i种彩珠的数目。接下来按升序给出Ti个非负整数，为这Ti个彩珠分别出现的位置。

Output

应包含一行，为最短彩带长度。

Sample Input

6 3

1 5

2 1 7

3 1 3 8

Sample Output

3

HINT

有多种方案可选，其中比较短的是1~5和5~8。后者长度为3最短。

【数据规模】

对于50%的数据， N≤10000；

对于80%的数据， N≤800000；

对于100%的数据，1≤N≤1000000，1≤K≤60，0≤彩珠位置<2^31。

 

唉，二分答案都没想到，思路有点不清晰啊

1 const  2     maxn=1000010;  3     maxk=65;  4 type  5     node=record  6       x,k:longint;  7     end;  8 var  9     a:array[0..maxn]of node; 10     n,k:longint; 11  12 operator <(a,b:node)c:boolean; 13 begin 14     c:=a.k
      
       >1]; 32     repeat 33       while a[i]
       
        j; 44     if i
        
         l then sort(l,j); 46 end; 47  48 procedure init; 49 var 50     i,j,x:longint; 51 begin 52     read(k,k); 53     for i:=1 to k do 54       begin 55         read(x); 56         for j:=1 to x do 57           begin 58             inc(n); 59             read(a[n].k); 60             a[n].x:=i; 61           end; 62       end; 63     sort(1,n); 64 end; 65  66 function flag(len:longint):boolean; 67 var 68     l,r,s:longint; 69     cnt:array[0..maxk]of longint; 70 begin 71     l:=1; 72     r:=0; 73     s:=0; 74     fillchar(cnt,sizeof(cnt),0); 75     while  r
         
          len do 81           begin 82             dec(cnt[a[l].x]); 83             if cnt[a[l].x]=0 then dec(s); 84             inc(l); 85           end; 86         if s=k then exit(true); 87       end; 88     exit(false); 89 end; 90  91 procedure work; 92 var 93     l,r,mid:longint; 94 begin 95     l:=0; 96     r:=a[n].k-a[1].k; 97     while l<>r do 98       begin 99         mid:=longint((int64(l)+r)>>1);100         if flag(mid) then r:=mid101         else l:=mid+1;102       end;103     write(l);104 end;105 106 begin107     init;108     work;109 end.