#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>

FILE* fin;

int per [16][16];
int cost [16][16][32];
int n, k;

int was [16][1024];

int Find (int day, int f, int t)
{
   if ( day == k )  return ( f == t ) ? 0 : -1;

   if ( was [f][day] > 0 )  return was [f][day];
   
   int min = 0x7FFFFFFF;
   for ( int i = 0;  i < n;  ++i )
   {
      int c = cost[f][i][day%per[f][i]];
      if ( c > 0 )
      {
         int pokr = Find (day+1, i, t);
         if ( pokr >= 0 && c + pokr < min )  min = c + pokr;
      }
   }
   
   min = ( min == 0x7FFFFFFF ) ? -1 : min;
   was[f][day] = min;
   return min;
}


int main (void)
{
   fin = fopen ("ontherun.in", "rt");
   
   for ( int probn = 1;  ;  ++probn )
   {
      fscanf(fin, "%d%d",&n,&k);
      if(n==0 && k==0) break;
    
      memset (&was, 0, sizeof (was));

      for ( int i = 0;  i < n;  ++i )
         for ( int j = 0;  j < n;  ++j )
            if ( i == j )
            {
               per[i][j] = 1;
               cost[i][j][0] = 0;
            }
            else
            {
               fscanf (fin, "%d", & (per[i][j]));
               for ( int ii = 0;  ii < per[i][j];  ++ii )
                  fscanf (fin, "%d", & (cost[i][j][ii]));
            }
            
       int res = Find (0, 0, n-1);

    
      printf("Scenario #%d\n", probn);
      if ( res > 0 ) printf("The best flight costs %d.\n\n", res);
      else printf("No flight possible.\n\n");
   }

   fclose (fin);
   return 0;
}