/* Stamps
   The problem statement is a bit vague. We're supposed to compute the
maximal coverage for each stamp denomination scheme, and output the coverage
and the scheme with highest maximal coverage. The problem is ambiguous in
the case when two schemes have the same coverage. The way this solution is
written, whichever scheme has the least number of stamps is output. If both
schemes have the same number of stamps, then output whichever was input
first. */

#define S 10       /* max # of denominations per scheme */
#define N 10       /* max number of schemes */
#define MAX 100    /* max denomination */

int denom[N][S];   /* denom[i][k] is denomination of stamp k from scheme i */
int num[N];        /* num[i] is number of denominations in scheme i */
int cover[N];      /* cover[i] is maximum cover of scheme i */

void process(int i, int s)
/* assigns to cover[i] the maximum cover of stamp scheme i */
{
int size;          /* maximum possible cover possible with stamps */
int j;             /* index through coverable amounts */
int k;             /* index through stamp denominations */
int array[S*MAX];  /* array[j] is # of stamps required to cover j cents */

size = denom[i][num[i]-1] * s + 1;   /* maximum possible cover */
for (j = 0; j < size; j++)           /* initialize to all uncovered denoms */
   array[j] = 0;
for (k = 0; k < num[i]; k++)         /* can cover denoms that are stamps */
   array[denom[i][k]] = 1;
for (j = 1; j < size; j++)
   {
   if (array[j] == 0)
      break;
   for (k = 0; k < num[i]; k++)
      if (j+denom[i][k] < size)
         if (array[j] < s)
            if ((array[j+denom[i][k]] == 0) ||
                (array[j+denom[i][k]] > array[j]+1))
               array[j+denom[i][k]] = array[j] + 1;
   }
/* j is index of first amount we can't cover */
cover[i] = j-1;
}

void main(void)
{
int s;    /* maximum number of stamps on an envelope */
int n;    /* number of schemes */
int i;    /* scheme index */
int j;
int m;    /* index of scheme with max cover */

do {
   scanf("%d", &s);
   if (s == 0) break;
   scanf("%d", &n);
   for (i = 0; i < n; i++)
      {
      scanf("%d", &(num[i]));
      for (j = 0; j < num[i]; j++)
         scanf("%d", &(denom[i][j]));
      process(i, s);
      }
   m = 0;
   for (i = 1; i < n; i++)
      if ((cover[i] > cover[m]) ||
          ((cover[i] == cover[m]) && (num[i] < num[m])))
         m = i;
   printf("max coverage = %3d : ", cover[m]);
   for (j = 0; j < num[m]; j++)
      printf("%3d", denom[m][j]);
   printf("\n");
   } while (1);
}