/* Uždavinio autorius: Dr. Mindaugas Plukas, VU MIF dėstytojas;
   Sprendimą bei testus parengė: Dr. Mindaugas Plukas */ 


#include <stdlib.h>
#include <stdio.h>


#define MAX_KAMBARIU 80

short perejimai[MAX_KAMBARIU][MAX_KAMBARIU] ; 
/* perėjimai[I][J] = 1 <=> yra perėjimas iš kambario I į J 
   perėjimai[I][J] = 0 <=> nera perėjimo iš kambario I į J */
   
int taskai[MAX_KAMBARIU] ;
/* taškai[I] - taškai (prizas arba bauda ) kambaryje I */

int isrKamb[MAX_KAMBARIU] ;
/* isrKamb - topologiškai išrūšiuotų kambarių numerių masyvas; t.y
   k < l => nėra kelio iš kambario isrKamb[l] į kambarį isrKamb[k] */    

int maxTasku[MAX_KAMBARIU] ;
/* maxTasku[I] - kiek maksimaliai taškų galima gauti, baigiant kelionę šiame kambaryje
   (o pradedant bet kuriame kambaryje) */

int N = 0 ; /* Kambarių skaičius */


/* Topologiškai rikiuoja labirintą */
void topolRusiuok( void ) ;

void main()
{
   FILE *fpDuom = NULL ;
   FILE *fpRez = NULL ;
   
   int i = 0, j = 0, k = 0 ; 
   int maxTaskuLabirinte = 0 ; 
   
   /* Nuskaitom duomenis */
   fpDuom = fopen( "LABIRINT.DAT", "r" ) ;
   fscanf( fpDuom, " %d ", &N ) ;
   
   for ( i = 0 ; i < N ; i ++ )
    for ( j = 0 ; j < N ; j ++ )
      perejimai[i][j] = 0 ;
     
   for ( i = 0 ; i < N ; i ++ )
    {
      int P = 0 ;
      fscanf( fpDuom, " %d ", &taskai[i] ) ;
      fscanf( fpDuom, " %d ", &P ) ;
      for ( k = 0 ; k < P ; k ++ )
       {
         fscanf( fpDuom, " %d ", &j ) ;
         perejimai[i][j-1] = 1 ;
       }  
    }
    
   fclose( fpDuom ) ;

   /* Topologiškai išrikiuojam kambarius */
   topolRusiuok() ;

   /* Kambarius apdorojame topologinio rikiavimo tvarka(pradėdami nuo kambario(-iu) 
      į kuriuos nėra įeinančių perėjimų);
      kiekvienam kambariui surandam kiek max taškų galima surinkti, baigiant kelionę
      jame( o pradedant viename iš topologiškai pirmesnių kambarių) */
   for ( k = 0 ; k < N ; k ++ )
    {
       i = isrKamb[k] ;
       maxTasku[i] = taskai[i] ;
       for ( j = 0 ; j < N ; j ++ )
        if ( perejimai[j][i] ) /* iš kambario j yra perėjimas į kambarį i */
         {
           if ( maxTasku[j] + taskai[i] > maxTasku[i] )
             maxTasku[i] = maxTasku[j] + taskai[i] ; 
         }
    }

   /* Surandam, kiek maksimaliai taškų galima surinkti labirinte */
   maxTaskuLabirinte = maxTasku[0] ; 
   for ( i = 1 ; i < N ; i ++ )
    {
      if ( maxTaskuLabirinte < maxTasku[i] )
        maxTaskuLabirinte = maxTasku[i] ;
    }

   /* Išvedam rezultatus */ 
   fpRez = fopen( "LABIRINT.REZ", "w" ) ;
   fprintf( fpRez, "%d\n", maxTaskuLabirinte ) ;
   fclose( fpRez ) ;

}



/* Topologinis labirinto rikiavimas */


/* Kambariu stekas */
int kambariuStekas[MAX_KAMBARIU] ;
int stekoVirsus = 0 ;

void ST_istustink( void )
{
  stekoVirsus = 0 ;
}

short ST_tuscias( void )
{
  if ( stekoVirsus == 0 )
    return 1 ;
  else  
    return 0 ;
}

void ST_dek( int i )
{
  kambariuStekas[stekoVirsus] = i ;
  stekoVirsus ++ ;
}

int ST_imk( void )
{
  stekoVirsus -- ;
  return kambariuStekas[stekoVirsus] ;
}
/* Kambarių steko apibrėžimo pabaiga */


int ieinanciuPerejimu[MAX_KAMBARIU] ;
/* įeinančiųPerėjim[I] - kiek perėjimų įeina į kambarį I */

void topolRusiuok( void )
{
   int i = 0, j = 0 ;
   int num = 0 ;
   
   /* Suskaičiuojam kiek perėjimų įeina į kiekvieną kambarį */
   for ( i = 0 ; i < N ; i ++ )
    {
      ieinanciuPerejimu[i] = 0 ;
      for ( j = 0 ; j < N ; j ++ )
       if ( perejimai[j][i] )
         ieinanciuPerejimu[i] ++ ;
    }

   /* Sudedam į steką visus kambarius, į kuriuos nėra perėjimų
      ( privalo būti bent vienas toks kambarys ) */
   ST_istustink() ;
   for ( i = 0 ; i < N ; i ++ )
    if ( ieinanciuPerejimu[i] == 0 )
      ST_dek( i ) ;
     
   /* Numeruojam pradėdami nuo kambarių į kuriuos nėra perėjimų ir 
      sunumeruotus kambarius "šalinam" iš labirinto */
   num = 0 ;  
   while ( ! ST_tuscias() )
    {
      i = ST_imk() ;
      isrKamb[num] = i ;
      num ++ ;

      for ( j = 0 ; j < N ; j ++ )
       if ( perejimai[i][j] )
        {
          ieinanciuPerejimu[j] -- ;
          if ( ieinanciuPerejimu[j] == 0 )
            ST_dek( j ) ;
        }  
    }  
}