using System; using static System.Console; using System.Linq; using System.Collections.Generic; class Program { static int NN => int.Parse(ReadLine()); static int[] NList => ReadLine().Split().Select(int.Parse).ToArray(); static int[] NMi => ReadLine().Split().Select(c => int.Parse(c) - 1).ToArray(); static int[][] NMap(int n) => Enumerable.Repeat(0, n).Select(_ => NMi).ToArray(); public static void Main() { Solve(); } static void Solve() { var c = NList; var (n, m) = (c[0], c[1]); var a = NList; var b = NList; var map = NMap(m); var g = new MaxFlowGraph(n + m + 2); var s = n + m; for (var i = 0; i < n; ++i) { g.AddEdge(i, s + 1, a[i]); } for (var i = 0; i < m; ++i) { g.AddEdge(s, n + i, b[i]); for (var j = 1; j < map[i].Length; ++j) { g.AddEdge(n + i, map[i][j], int.MaxValue); } } var ans = - g.Flow(s, s + 1); foreach (var bi in b) ans += bi; WriteLine(ans); } // 最大フローグラフ // MaxFlowGraph(n) n:頂点数 // AddEdge(from, to, cap) from,to:0-indexed cap:最大用量 // Flow(from, to) 最大流量を求める 各辺の流量を変更 // Flow(from, to, flowLimit) // MinCut(from) Flow(最小カット)実行後の残余グラフで各頂点への到達可能性を取得 // GetEdge(i), GetEdges() 内部の辺の状態を取得 // ChangeEdge(i, newCap, newFlow) 対象辺の流量を変更 class MaxFlowGraph { int _n; long max = long.MaxValue; class EdgeI { public int to { get; private set; } public int rev { get; private set; } public long cap { get; set; } public EdgeI(int to, int rev, long cap) { this.to = to; this.rev = rev; this.cap = cap; } } List> pos = new List>(); List[] g; public MaxFlowGraph(int n) { _n = n; g = new List[n]; for (var i = 0; i < n; ++i) g[i] = new List(); } public int AddEdge(int from, int to, long cap) { var m = pos.Count; pos.Add(new KeyValuePair(from, g[from].Count)); g[from].Add(new EdgeI(to, g[to].Count, cap)); g[to].Add(new EdgeI(from, g[from].Count - 1, 0)); return m; } public class Edge { public int from { get; private set; } public int to { get; private set; } public long cap { get; private set; } public long flow { get; private set; } public Edge(int from, int to, long cap, long flow) { this.from = from; this.to = to; this.cap = cap; this.flow = flow; } } public Edge GetEdge(int i) { var m = pos.Count; var e = g[pos[i].Key][pos[i].Value]; var re = g[e.to][e.rev]; return new Edge(pos[i].Key, e.to, e.cap + re.cap, re.cap); } public List GetEdges() { var m = pos.Count; var result = new List(); for (var i = 0; i < m; ++i) result.Add(GetEdge(i)); return result; } public void ChangeEdge(int i, long new_cap, long new_flow) { var m = pos.Count; var e = g[pos[i].Key][pos[i].Value]; var re = g[e.to][e.rev]; e.cap = new_cap - new_flow; re.cap = new_flow; } public long Flow(int s, int t) { return Flow(s, t, max); } public long Flow(int s, int t, long limit) { var level = new int[_n]; var iter = new int[_n]; var que = new Queue(); void bfs() { for (var i = 0; i < _n; ++i) level[i] = -1; level[s] = 0; que.Clear(); que.Enqueue(s); while (que.Count > 0) { var v = que.Dequeue(); foreach (var e in g[v]) { if (e.cap == 0 || level[e.to] >= 0) continue; level[e.to] = level[v] + 1; if (e.to == t) return; que.Enqueue(e.to); } } } long dfs(int v, long up) { if (v == s) return up; long res = 0; var level_v = level[v]; for (var i = iter[v]; i < g[v].Count; ++i) { var e = g[v][i]; if (level_v <= level[e.to] || g[e.to][e.rev].cap == 0) continue; long d = dfs(e.to, Min(up - res, g[e.to][e.rev].cap)); if (d <= 0) continue; g[v][i].cap += d; g[e.to][e.rev].cap -= d; res += d; if (res == up) break; } return res; } long flow = 0; while (flow < limit) { bfs(); if (level[t] == -1) break; for (var i = 0; i < iter.Length; ++i) iter[i] = 0; while (flow < limit) { var f = dfs(t, limit - flow); if (f == 0) break; flow += f; } } return flow; } long Min(long a, long b) { return a.CompareTo(b) < 0 ? a : b; } public bool[] MinCut(int s) { var visited = new bool[_n]; var que = new Queue(); que.Enqueue(s); while (que.Count > 0) { var p = que.Dequeue(); visited[p] = true; foreach (var e in g[p]) { if (e.cap != 0 && !visited[e.to]) { visited[e.to] = true; que.Enqueue(e.to); } } } return visited; } } }