Problem: Wind Corridor is a covered passageway where strong wind is always blowing. It is a long corridor of width W, and there are several pillars in it. Each pillar is a right prism and its face is a polygon (not necessarily convex).

In this problem, we consider two-dimensional space where the positive x-axis points the east and the positive y-axis points the north. The passageway spans from the south to the north, and its length is infinity. Specifically, it covers the area 0 ≤ x ≤ W. The outside of the passageway is filled with walls. Each pillar is expressed as a polygon, and all the pillars are located within the corridor without conflicting or touching each other.

Wind blows from the south side of the corridor to the north. For each second, w unit volume of air can be flowed at most if the minimum width of the path of the wind is w. Note that the path may fork and merge, but never overlaps with pillars and walls.

Your task in this problem is to write a program that calculates the maximum amount of air that can be flowed through the corridor per second.



Input

The input consists of multiple datasets. Each dataset has the following format:

The first line of the input contains two integers W and N. W is the width of the corridor, and N is the number of pillars. W and N satisfy the following condition: 1 ≤ W ≤ 104 and 0 ≤ N ≤ 200.

Then, N specifications of each pillar follow. Each specification starts with a line that contains a single integer M, which is the number of the vertices of a polygon (3 ≤ M ≤ 40). The following M lines describe the shape of the polygon. The i-th line (1 ≤ i ≤ M) contains two integers xi and yi that denote the coordinate of the i-th vertex (0 < xi < W, 0 < yi < 104).

The last dataset is followed by a line containing two zeros. This line is not a part of any dataset and should not be processed.

Output

For each dataset, your program should print a line that contains the maximum amount of air flow per second, in unit volume. The output may contain arbitrary number of digits after the decimal point, but the absolute error must not exceed 10-6.

Example

Input

5 2
4
1 1
1 2
2 2
2 1
4
3 3
3 4
4 4
4 3
0 0


Output

3.41421356

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
      
#define FOR(i,a,b) for( ll i = (a); i < (ll)(b); i++ )
#define REP(i,n) FOR(i,0,n)
#define YYS(x,arr) for(auto& x:arr)
#define ALL(x) (x).begin(),(x).end()
#define SORT(x) sort( (x).begin(),(x).end() )
#define REVERSE(x) reverse( (x).begin(),(x).end() )
#define UNIQUE(x) (x).erase( unique( ALL( (x) ) ) , (x).end() )
#define PW(x) (1LL<<(x))
#define SZ(x) ((ll)(x).size())
#define SHOW(x) cout << #x << " = " << x << endl
#define SHOWA(x,n) for( int yui = 0; yui < n; yui++ ){ cout << x[yui] << " "; } cout << endl

#define pb emplace_back
#define fi first
#define se second

using namespace std;

typedef long double ld;
typedef long long int ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<ld> vd;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<vpl> gr;
typedef vector<vl> ml;
typedef vector<vd> md;
typedef vector<vi> mi;
     
const ll INF = (ll)1e9 + 10;
const ll INFLL = (ll)1e18 + 10;
const ld EPS = 1e-12;
const ll MOD = 1e9+7;
     
template<class T> T &chmin( T &a , const T &b ){ return a = min(a,b); }
template<class T> T &chmax( T &a , const T &b ){ return a = max(a,b); }
template<class T> inline T sq( T a ){ return a * a; }

ll in(){ long long int x; scanf( "%lld" , &x ); return x; }
char yuyushiki[1000010]; string stin(){ scanf( "%s" , yuyushiki ); return yuyushiki; }

// head

#define X real()
#define Y imag()

#define curr(P,i) P[i]
#define next(P,i) P[(i+1)%P.size()]

typedef complex<ld> P;
typedef vector<P> Pol;

namespace std{
  template<class T> bool operator<(const complex<T> &a , const complex<T> &b ){
    return a.X == b.X ? a.Y < b.Y : a.X < b.X;
  }
}

const ld PI = atan(1)*4.0;

struct L : public vector<P> {
  L( const P a , const P b ){
    pb( a ); pb( b );
  }
  L(){}
};

struct C{
  P p; ld r;
  C( const P p , ld r ) : p(p) , r(r) {}
  C(){}
};

inline ld det( const P &a , const P &b ){
  return imag(conj(a)*b);
}
inline ld dot( const P &a , const P &b ){
  return real(conj(a)*b);
}

inline P unit( const P &a ){
  return a / abs( a );
}

inline ld arg( const P &p ){
  return atan2l( p.Y , p.X );
}

inline P ort( P a ){
  return P( -a.Y , a.X );
}

inline P mid( const P a , const P b ){
  return ( a + b ) * (ld)0.5;
}

ld dtor( ld d ){
  return d * PI / 180.0;
}

int ccw( P a , P b , P c ){
  b -= a; c -= a;
  if( det( b , c ) >  EPS )     return +1; // counter clockwise
  if( det( b , c ) < -EPS )     return -1; // clockwise
  if( dot( b , c ) < -EPS )     return +2; // c--a--b on line
  if( norm(b) < norm(c) - EPS ) return -2; // a--b--c on line
  return 0;
}

bool intersectLL( const L &l , const L &m ){
  return abs( det( l[1] - l[0] , m[1] - m[0] ) ) > EPS || abs( det( l[1] - l[0] , m[0] - l[0] ) ) < EPS;
}

bool parallel( const L l , const L m ){
  return abs( det( l[1] - l[0] , m[1] - m[0] ) ) < EPS;
}

bool intersectSP( const L &s , const P &p ){
  return abs( s[0] - p ) + abs( s[1] - p ) - abs( s[1] - s[0] ) < EPS;
}

bool intersectLP( const L l , const P p ){
  return abs( det( l[1] - p , l[0] - p ) ) < EPS;
}

// including touch
bool intersectSS( const L s , const L t ){
  return ccw( s[0] , s[1] , t[0] ) * ccw( s[0] , s[1] , t[1] ) <= 0 && ccw( t[0] , t[1] , s[0] ) * ccw( t[0] , t[1] , s[1] ) <= 0;
}

bool intersectLS( const L l , const L s ){
  return det( l[1] - l[0] , s[0] - l[0] ) * det( l[1] - l[0] , s[1] - l[0] ) < EPS;
}

P projection( const L &l , const P &p ){
  ld t = dot( p - l[0] , l[1] - l[0] ) / norm( l[1] - l[0] );
  return l[0] + t * ( l[1] - l[0] );
}

P symmetry( const L l , const P p ){
  P proj = projection( l , p );
  return proj + ( proj - p );
}

ld distanceSP( const L &s , const P &p ){
  const P r = projection( s , p );
  if( intersectSP( s , r ) ) return abs( r - p );
  return min( abs( s[0] - p ) , abs( s[1] - p ) );
}

ld distanceLP( const L &s , const P &p ){
  return abs( p - projection(s,p) );
}

ld distanceSS( const L s , const L t ){
  if( intersectSS( s , t ) ) return 0;
  return min( min( distanceSP( s , t[0] ) , distanceSP( s , t[1] ) ) , min( distanceSP( t , s[0] ) , distanceSP( t , s[1] ) ) );
}

P crosspoint( const L &l , const L &m ){
  ld a = det( l[1] - l[0] , m[1] - m[0] );
  ld b = det( l[1] - l[0] , l[1] - m[0] );
  if( abs(a) < EPS && abs(a) < EPS ) return m[0];
  if( abs(a) < EPS ) assert(false);
  return m[0] + b / a * (m[1]-m[0]);
}

P rotate( P p , ld t ){
  return p * exp( t * P( 0 , 1 ) );
}

Pol rotate( Pol pol , ld t ){
  YYS( p , pol ) p = rotate( p , t );
  return pol;
}

P rotate( P p , P c , ld t ){
  return rotate( p - c , t ) + c;
}

int getintersectCC( const C c , const C d ){
  ld di = abs( c.p - d.p );
  if( di < EPS && fabsl( c.r - d.r ) < EPS ) return -1; // same
  if( di < fabsl( c.r - d.r ) - EPS ) return 0; // completely inside
  if( di < fabsl( c.r - d.r ) + EPS ) return 1; // inscribed
  if( di < fabsl( c.r + d.r ) - EPS ) return 2; // intersect
  if( di < fabsl( c.r + d.r ) + EPS ) return 3; // outscribed
  return 4; // completely outside
}

// include touch
bool intersectCC( const C c , const C d ){
  int res = getintersectCC( c , d );
  return 1 <= res && res <= 3;
}

pair<P,P> crosspoint( const C c , const C d ){
  int res = getintersectCC( c , d );
  assert( 1 <= res && res <= 3 );
  if( res == 1 || res == 3 ){
    P p = c.p + unit( d.p - c.p ) * c.r;
    if( abs( d.p - p ) < d.r - EPS ) p = c.p + unit( c.p - d.p ) * c.r;
    return make_pair( p , p );
  }
  ld di = abs( c.p - d.p );
  ld a = acos(( c.r * c.r + di * di - d.r * d.r ) / ( 2 * c.r * di ));
  ld t = arg( d.p - c.p );
  return make_pair( c.p + rotate( P( c.r , 0 ) , t+a ) , c.p + rotate( P( c.r , 0 ) , t-a ) );
}

int intersectCL( const C &c , const L &l ){
  ld di = distanceLP( l , c.p );
  if( di < c.r - EPS ) return 1; // completely intersect
  if( di < c.r + EPS ) return 2; // touch
  return 0;
}

pair<P,P> crosspoint( const C &c , const L &l ){
  assert( intersectCL( c , l ) );
  P pr = projection( l , c.p );
  P e = unit( l[0] - l[1] );
  ld base = sqrtl( c.r * c.r - norm( pr - c.p ) );
  return make_pair( pr + e * base , pr - e * base );
}

int containCP( const C &c , const P &p ){
  ld di = abs( c.p - p );
  if( di < c.r - EPS ) return 1; // completely inside
  if( di < c.r + EPS ) return 2; // touch
  return 0;
}

pair<P,P> tangent_point( const C c , const P p ){
  return crosspoint( c , C( mid(c.p,p) , abs(p-c.p)/2 ) );
}

pair<L,L> tangent( const C c , const P p ){
  pair<P,P> cp = tangent_point( c , p );
  return make_pair( L( p , cp.fi ) , L( p , cp.se ) );
}

// First : left , second : right
vector<Pol> convex_cut( const Pol pol, L l ){
  vector<Pol> Q(2);
  REP( i , pol.size() ){
    P a = curr(pol,i), b = next(pol,i);
    if( ccw(l[0] , l[1] , a ) != -1 ) Q[0].pb( a );
    if( ccw(l[0] , l[1] , a ) != 1  ) Q[1].pb( a );
    if( ccw(l[0] , l[1] , a )*ccw(l[0] , l[1] , b ) < 0 ){
      Q[0].pb( crosspoint( L(a,b) , l ) );
      Q[1].pb( crosspoint( L(a,b) , l ) );
    }
  }
  return Q;
}

ld area( const Pol &pol ){
  ld a = 0;
  REP( i , pol.size() ) a += det( curr(pol,i) , next(pol,i) );
  return a/2;
}

enum{ OUT , ON , IN };
int contains( const Pol pol, const P p) {
  bool in = false;
  REP( i , SZ(pol) ){
    P a = curr(pol,i) - p, b = next(pol,i) - p;
    if (imag(a) > imag(b)) swap(a, b);
    if (imag(a) < EPS && EPS < imag(b))
      if( det(a, b) < -EPS) in = !in;
    if( abs( det( a , b ) ) < EPS && dot( a , b ) < EPS ) return ON;
  }
  return in ? IN : OUT;
}

P bisector( P a , P b ){
  P res = unit(a) + unit(b); // making diamond
  return unit( res );
}


L parp( const P p , const P q ){
  P md = mid( p , q );
  P d = rotate( unit( q - p ) , PI / 2 );
  return L( md , md + d );
}

P sym( const L l , const P p ){
  P pr = projection( l , p );
  return p + ld(2) * ( pr - p );
}


Pol convex_hull( vector<P> ps ){
  int n = SZ(ps);
  int k = 0;
  SORT( ps );
  Pol ch( 2*n );
  for( int i = 0; i < n; ch[k++] = ps[i++] )
    while( k >= 2 && ccw( ch[k-2] , ch[k-1] , ps[i] ) <= 0 ) k--;
  for( int i = n-2, t = k+1; i >= 0; ch[k++] = ps[i--] )
    while( k >= t && ccw( ch[k-2] , ch[k-1] , ps[i] ) <= 0 ) k--;
  ch.resize( k-1 );
  return ch;
}


template<typename T>
struct Dijkstra{
  typedef pair<int,T> pit;
  typedef pair<T,int> pti;  
  const T INFT;
  vector<vector<pit> > G;
  vector<T> dist;
  int n;
  Dijkstra( T INFT ) : INFT(INFT) {}
  void init( int arg_n ){
    n = arg_n;
    G = vector<vector<pit> >( n , vector<pit>(0) );
  }
  void add_biedge( int fr , int to , T co ){
    G[fr].pb( to , co );
    G[to].pb( fr , co );
  }
  void add_edge( int fr , int to , T co ){
    G[fr].pb( to , co );
  }
  T dijkstra( int s , int t = -1 ){
    dist = vector<T>( n , INFT );
    dist[s] = 0;
    priority_queue<pti,vector<pti>,greater<pti> > que;
    que.emplace( 0 , s );
    while( !que.empty() ){
      T d = que.top().fi;
      int p = que.top().se;
      que.pop();
      if( d > dist[p] ){
	continue;
      }
      if( p == t ){
	return d;
      }
      YYS( w , G[p] ){
	int to = w.fi;
	T co = w.se;
	if( d + co < dist[to] ){
	  dist[to] = d + co;
	  que.emplace( dist[to] , to );
	}
      }
    }
    return INFT;
  }
};

int w, n;

Dijkstra<ld> dij(INFLL);

Pol p[210];

int main(){

  while( 1 ){
    w = in();
    n = in();
    if( w == 0 && n == 0 ){
      break;
    }
  
    dij.init( n + 2 );

    REP( i , n ){
      p[i].clear();
      int m = in();
      REP( j , m ){
        int x = in();
        int y = in();
        p[i].pb( x, y );
        dij.add_biedge( i, n, x );
        dij.add_biedge( i, n+1, w-x );
      }
    }

    REP( i , n ){
      REP( j , i ){
        REP( k , SZ(p[i]) ){
          REP( l , SZ(p[j]) ){
            L s( curr(p[i], k), next(p[i], k) );
            L t( curr(p[j], l), next(p[j], l) );
            dij.add_biedge( i, j, distanceSS(s, t) );
          }
        }
      }
    }

    dij.add_biedge(n, n+1, w);

    printf( "%.18lf\n", (double)dij.dijkstra( n, n+1 ) );
  }
  
  return 0;
}