using System; using System.Collections.Generic; using System.Linq; using System.IO; using System.Runtime.CompilerServices; using System.Text; using System.Numerics; using static Template; using static System.Console; using static System.Convert; using static System.Math; using Pi = Pair; class Solver { public void Solve(Scanner sc) { int W, N, M; sc.Make(out W, out N); var J = sc.ArrInt; M = sc.Int; var C = sc.ArrInt; var f = new MaxFlow(N + M + 2); for (var i = 0; i < N; i++) f.AddDirectedEdge(N + M, i, J[i]); for (var i = 0; i < M; i++) f.AddDirectedEdge(N + i, N + M + 1, C[i]); var edge = Create(N, () => Create(M, () => 1)); for(var i = 0; i < M; i++) { int Q = sc.Next(); for(var j = 0; j < Q; j++) { edge[sc.Next() - 1][i] = 0; } } for (var i = 0; i < N; i++) for (var j = 0; j < M; j++) f.AddDirectedEdge(i, N + j, edge[i][j] * J[i]); WriteLine(f.Execute(N + M, N + M + 1) >= W ? "SHIROBAKO" : "BANSAKUTSUKITA"); } } public class MaxFlow { readonly List[] G; readonly int[] lv, iter; public MaxFlow(int V) { G = new List[V]; lv = new int[V]; iter = new int[V]; for (int i = 0; i < G.Length; i++) G[i] = new List(); } public void AddDirectedEdge(int from, int to, int cap) => addEdge(from, to, cap, 0); public void AddUndirectedEdge(int from, int to, int cap) => addEdge(from, to, cap, cap); void addEdge(int f, int t, int c1, int c2) { var a = new Edge(t, c1); var b = new Edge(f, c2); Edge.Link(a, b); G[f].Add(a); G[t].Add(b); } public int Execute(int src, int sink, int f = -1) { int flow = 0; if (f < 0) f = int.MaxValue; while (f > 0) { bfs(src); if (lv[sink] == 0) return flow; Array.Clear(iter, 0, iter.Length); int df; while ((df = dfs(src, sink, f)) > 0) { flow += df; f -= df; } } return flow; } void bfs(int s) { Array.Clear(lv, 0, lv.Length); var q = new Queue(); lv[s] = 1; q.Enqueue(s); while (q.Count > 0) { var v = q.Dequeue(); foreach (var e in G[v]) if (e.Cap > 0 && lv[e.To] == 0) { lv[e.To] = lv[v] + 1; q.Enqueue(e.To); } } } int dfs(int v, int t, int f) { if (v == t) return f; int ret = 0; for (; iter[v] < G[v].Count; iter[v]++) { var e = G[v][iter[v]]; if (e.Cap <= 0 || lv[v] >= lv[e.To]) continue; int df = dfs(e.To, t, Math.Min(f, e.Cap)); if (df <= 0) continue; e.Cap -= df; e.Rev.Cap += df; ret += df; f -= df; if (f == 0) break; } return ret; } class Edge { public static void Link(Edge e1, Edge e2) { e1.Rev = e2; e2.Rev = e1; } public int To { get; private set; } public Edge Rev { get; private set; } public int Cap { get; set; } public Edge(int t, int c) { To = t; Cap = c; } public override string ToString() { return string.Format("to: {0}, cap: {1}", To, Cap); } } } #region Template public static class Template { static void Main(string[] args) { Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }); new Solver().Solve(new Scanner()); Console.Out.Flush(); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static bool chmin(ref T a, T b) where T : IComparable { if (a.CompareTo(b) == 1) { a = b; return true; } return false; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static bool chmax(ref T a, T b) where T : IComparable { if (a.CompareTo(b) == -1) { a = b; return true; } return false; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static void swap(ref T a, ref T b) { var t = b; b = a; a = t; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static T[] Create(int n, Func f) { var rt = new T[n]; for (var i = 0; i < rt.Length; ++i) rt[i] = f(); return rt; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static T[] Create(int n, Func f) { var rt = new T[n]; for (var i = 0; i < rt.Length; ++i) rt[i] = f(i); return rt; } public static void Fail(T s) { Console.WriteLine(s); Console.Out.Close(); Environment.Exit(0); } } public class Scanner { public string Str => Console.ReadLine().Trim(); public int Int => int.Parse(Str); public long Long => long.Parse(Str); public double Double => double.Parse(Str); public int[] ArrInt => Str.Split(' ').Select(int.Parse).ToArray(); public long[] ArrLong => Str.Split(' ').Select(long.Parse).ToArray(); public char[][] Grid(int n) => Create(n, () => Str.ToCharArray()); public int[] ArrInt1D(int n) => Create(n, () => Int); public long[] ArrLong1D(int n) => Create(n, () => Long); public int[][] ArrInt2D(int n) => Create(n, () => ArrInt); public long[][] ArrLong2D(int n) => Create(n, () => ArrLong); private Queue q = new Queue(); [MethodImpl(MethodImplOptions.AggressiveInlining)] public T Next() { if (q.Count == 0) foreach (var item in Str.Split(' ')) q.Enqueue(item); return (T)Convert.ChangeType(q.Dequeue(), typeof(T)); } public void Make(out T1 v1) => v1 = Next(); public void Make(out T1 v1, out T2 v2) { v1 = Next(); v2 = Next(); } public void Make(out T1 v1, out T2 v2, out T3 v3) { Make(out v1, out v2); v3 = Next(); } public void Make(out T1 v1, out T2 v2, out T3 v3, out T4 v4) { Make(out v1, out v2, out v3); v4 = Next(); } public void Make(out T1 v1, out T2 v2, out T3 v3, out T4 v4, out T5 v5) { Make(out v1, out v2, out v3, out v4); v5 = Next(); } public void Make(out T1 v1, out T2 v2, out T3 v3, out T4 v4, out T5 v5, out T6 v6) { Make(out v1, out v2, out v3, out v4, out v5); v6 = Next(); } //public (T1, T2) Make() { Make(out T1 v1, out T2 v2); return (v1, v2); } //public (T1, T2, T3) Make() { Make(out T1 v1, out T2 v2, out T3 v3); return (v1, v2, v3); } //public (T1, T2, T3, T4) Make() { Make(out T1 v1, out T2 v2, out T3 v3, out T4 v4); return (v1, v2, v3, v4); } } public class Pair : IComparable> { public T1 v1; public T2 v2; public Pair() { } public Pair(T1 v1, T2 v2) { this.v1 = v1; this.v2 = v2; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public int CompareTo(Pair p) { var c = Comparer.Default.Compare(v1, p.v1); if (c == 0) c = Comparer.Default.Compare(v2, p.v2); return c; } public override string ToString() => $"{v1.ToString()} {v2.ToString()}"; public void Deconstruct(out T1 a, out T2 b) { a = v1; b = v2; } } public class Pair : Pair, IComparable> { public T3 v3; public Pair() : base() { } public Pair(T1 v1, T2 v2, T3 v3) : base(v1, v2) { this.v3 = v3; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public int CompareTo(Pair p) { var c = base.CompareTo(p); if (c == 0) c = Comparer.Default.Compare(v3, p.v3); return c; } public override string ToString() => $"{base.ToString()} {v3.ToString()}"; public void Deconstruct(out T1 a, out T2 b, out T3 c) { Deconstruct(out a, out b); c = v3; } } #endregion