1 #include <iostream>  2 #include <cstdlib>  3 #include <cstring>  4 #include <cstdio>  5 #include <queue>  6 const int inf = 1<<30 , N = 100 + 11 , M = 1000 + 11 ;  7 using namespace std ;  8 int m , n  ;  9 int head[N] , tot ; 10 struct id 11 { 12     int to , nxt , val ; 13 } edge[(N*N)<<1] ; 14 int dis[N*M] , cur[N*M] , num[M] , fir[M] , edg[N]; 15 bool vis[M] , use[N][N];   16 queue< int > Q ; 17  18 inline void  Init( ) 19 { 20     freopen( "NSOOJ10745.in" , "r" , stdin ) ; 21     freopen( "NSOOJ10745.out" , "w" , stdout ) ; 22 } 23  24  25 int read(  ) 26 { 27     char ch = getchar(  ) ; int k = 1 , ret = 0 ; 28     while( ch > ‘9‘ || ch < ‘0‘ ) { if( ch == ‘-‘ ) k = -1 ; ch = getchar( ) ; } 29     while( ch <= ‘9‘ && ch >= ‘0‘ ) ret = ret * 10 + ch - ‘0‘ , ch = getchar( ) ; 30     return ret * k ; 31 } 32  33  34 void add( int u , int v , int c ) 35 { 36     edge[++tot].to = v ; edge[tot].nxt = head[u] ; 37     edge[tot].val = c ; head[u] = tot ;  38 } 39  40 void input(  ) 41 { 42     m = read( ) , n = read( ) ; tot = 1 ; 43     memset( head , -1 , sizeof(head) ) ; 44     for( int x = 1 ; x <= m ; ++x ) 45         num[x] = read( ) ; 46     int a , b  ; 47     for( int x = 1 ;  x <= n ; ++x ) 48     { 49         a = read(  ) ; 50         for( int y = 1 ; y <= a ; ++y ) 51         { 52             b = read(  ) ; 53             if( !vis[b] ) 54             { 55                 if( !edg[x] )  56                 { 57                     add( 0 , x , num[b] ) ; 58                     edg[x] = tot ; 59                     add( x , 0 , 0 ) ; 60                 } 61                 else edge[edg[x]].val += num[b] ; 62                 fir[b] = x ; 63                 vis[b] = true ; 64             } 65             else 66             { 67                 if( use[fir[b]][x] ) continue ; 68                 add( fir[b] , x , inf ) ; 69                 add( x , fir[b] , 0 ) ; 70                 use[fir[b]][x] = true ; 71             } 72         } 73         b = read( ) ; 74         add( x , n + 1 , b ) ; 75         add( n+1 , x , 0 ) ; 76     } 77 } 78  79  80 bool bfs( )  81 { 82     memset( dis , -1 , sizeof(dis) ) ; 83     Q.push( 0 ) ; dis[0] = 0 ; 84     while( !Q.empty( ) )  85     { 86         int u = Q.front( ) ; Q.pop( ) ; 87         for( int i = head[u] ; ~i ; i = edge[i].nxt ) 88         { 89             int v = edge[i].to ; 90             if( dis[v] < 0 && edge[i].val > 0 ) 91             { 92                 dis[v] = dis[u] + 1 ; 93                 Q.push( v ) ; 94             } 95              96         } 97     } 98     if( dis[n+1] > 0 ) return true ; 99     return false ;100 }101  102  103 int dfs( int u , int inf )104 {105     if( u == n + 1 ) return inf ;106     int ans = 0 , cost = 0 ;107     for( int i = cur[u] ; ~i ; i = edge[i].nxt )108     {109         int v = edge[i].to ;110         if( dis[v] != dis[u] + 1 ) continue ;111         ans = dfs( v , min( inf - cost , edge[i].val ) ) ;112         edge[i].val -= ans ; edge[i^1].val += ans ;113         if( edge[i].val ) cur[u] = i ;114         cost += ans ;115         if( cost == inf ) return inf ;116     }117     if( !cost ) dis[u] = -1 ;118     return cost ;119 }120  121  122 123 void sov(  )124 {125     int ans = 0;126     while( bfs( ) )127     {128         for( int x = 0 ; x <= n + 1 ; ++x ) cur[x] = head[x] ;129         ans += dfs( 0 , inf ) ;130     }131     printf( "%d\n" , ans ) ;132 133 }134 135 136 int main(  )137 {138 //    Init(  ) ;139     input(  ) ;140     sov( ) ;141 //    fclose( stdin ) ;142 //    fclose( stdout ) ;143     return 0 ;144     145 }