#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using namespace placeholders; using LL = long long; using ULL = unsigned long long; using VI = vector< int >; using VVI = vector< vector< int > >; using VS = vector< string >; using SS = stringstream; using PII = pair< int, int >; using VPII = vector< pair< int, int > >; template < typename T = int > using VT = vector< T >; template < typename T = int > using VVT = vector< vector< T > >; template < typename T = int > using LIM = numeric_limits< T >; template < typename T > inline istream& operator>>( istream &s, vector< T > &v ){ for ( T &t : v ) { s >> t; } return s; } template < typename T > inline ostream& operator<<( ostream &s, const vector< T > &v ){ for ( int i = 0; i < int( v.size() ); ++i ){ s << ( " " + !i ) << v[i]; } return s; } template < typename T > inline T fromString( const string &s ) { T res; istringstream iss( s ); iss >> res; return res; }; template < typename T > inline string toString( const T &a ) { ostringstream oss; oss << a; return oss.str(); }; #define REP2( i, n ) REP3( i, 0, n ) #define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i ) #define GET_REP( a, b, c, F, ... ) F #define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2 )( __VA_ARGS__ ) #define FOR( e, c ) for ( auto &e : c ) #define ALL( c ) ( c ).begin(), ( c ).end() #define AALL( a, t ) ( t* )a, ( t* )a + sizeof( a ) / sizeof( t ) #define DRANGE( c, p ) ( c ).begin(), ( c ).begin() + p, ( c ).end() #define SZ( v ) ( (int)( v ).size() ) #define PB push_back #define EM emplace #define EB emplace_back #define BI back_inserter #define EXIST( c, e ) ( ( c ).find( e ) != ( c ).end() ) #define MP make_pair #define fst first #define snd second #define DUMP( x ) cerr << #x << " = " << ( x ) << endl // 最大流( Dinic 法 ) O( |E||V|^2 ) class Dinic { struct Edge { int to, cap, rev; Edge( int t, int c, int r ) : to( t ), cap( c ), rev( r ) {} }; vector< vector > G; vector distance, done; public: Dinic( int V ) : G( V ), distance( V ), done( V ) { return; } void connect( int from, int to, int cost ) { G[ from ].push_back( Edge( to, cost, G[ to ].size() ) ); G[ to ].push_back( Edge( from, 0, G[ from ].size() - 1 ) ); return; } int solve( int s, int t ) { int res = 0; while ( true ) { bfs( s ); if ( distance[t] < 0 ) { return res; } fill( done.begin(), done.end(), 0 ); for ( int f; ( f = dfs( s, t, numeric_limits::max() ) ) > 0; res += f ); } } private: void bfs( int s ) { fill( distance.begin(), distance.end(), -1 ); distance[s] = 0; queue que; que.push( s ); while ( !que.empty() ) { int v = que.front(); que.pop(); for ( int i = 0; i < (int)G[v].size(); ++i ) { Edge &e = G[v][i]; if ( e.cap > 0 && distance[ e.to ] < 0 ) { distance[ e.to ] = distance[v] + 1; que.push( e.to ); } } } return; } int dfs( int v, int t, int f ) { if ( v == t ) { return f; } for ( int &i = done[v]; i < (int)G[v].size(); ++i ) { Edge &e = G[v][i]; if ( e.cap > 0 && distance[v] < distance[ e.to ] ) { int d = dfs( e.to, t, min( f, e.cap ) ); if ( d > 0 ) { e.cap -= d; G[ e.to ][ e.rev ].cap += d; return d; } } } return 0; } }; // Dinic( |V| ) // connect( from, to, cap ) // solve( s, t ) int main() { cin.tie( 0 ); ios::sync_with_stdio( false ); int W; cin >> W; int N; cin >> N; VI J( N ); cin >> J; int M; cin >> M; VI C( M ); cin >> C; VVI table( N, VI( M, true ) ); REP( i, M ) { int q; cin >> q; REP( iter, q ) { int j; cin >> j; --j; table[j][i] = false; } } Dinic maxflow( N + M + 2 ); // [ 0, N ) := 原画 // [ N, N + M ) := 監督 const int SRC = N + M; const int SINK = SRC + 1; REP( i, N ) { maxflow.connect( SRC, i, J[i] ); } REP( i, M ) { maxflow.connect( N + i, SINK, C[i] ); } REP( i, N ) { REP( j, M ) { if ( table[i][j] ) { maxflow.connect( i, N + j, W ); } } } cout << ( maxflow.solve( SRC, SINK ) >= W ? "SHIROBAKO" : "BANSAKUTSUKITA" ) << endl; return 0; }