#include using namespace std; #define rep(i, n) for (ll i = 0; i < (ll)(n); i++) #define rep2(i, s, n) for (ll i = s; i <= (ll)(n); i++) #define rep3(i, s, n, d) for (ll i = s; i <= (ll)(n); i += d) #define rep4(i, s, n, d) for (ll i = s; i >= (ll)(n); i += d) typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef vector vi; typedef vector vvi; typedef vector vvvi; typedef vector vvvvi; typedef vector vs; typedef vector vvs; typedef vector vvvs; typedef vector vc; typedef vector vvc; typedef vector vvvc; typedef vector vll; typedef vector vvll; typedef vector vvvll; typedef vector vvvvll; typedef vector vd; typedef vector vvd; typedef vector vvvd; typedef vector vld; typedef vector vvld; typedef vector vvvld; typedef vector vb; typedef vector vvb; typedef vector vvvb; typedef vector> vpi; typedef vector> vpll; typedef pair pi; typedef vector vpi; typedef vector vvpi; typedef pair pll; typedef vector vpll; typedef vector vvpll; typedef tuple tui3; typedef tuple tull3; typedef priority_queue, greater> pqi; typedef priority_queue, greater> pqvi; typedef priority_queue, greater> pqll; typedef priority_queue, greater> pqvll; typedef priority_queue, greater> pqpll; typedef priority_queue, less> rpqpll; typedef priority_queue, less> rpqi; typedef priority_queue, less> rpqvi; typedef priority_queue, greater> pqtui3; typedef priority_queue, less> rpqtui3; typedef priority_queue, greater> pqtull3; typedef priority_queue, less> rpqtull3; #define yes(ans) if(ans)cout << "yes"<< endl; else cout << "no" << endl #define Yes(ans) if(ans)cout << "Yes"<< endl; else cout << "No" << endl #define YES(ans) if(ans)cout << "YES"<< endl ;else cout << "NO" << endl #define printv(vec) {rep(i, vec.size()) cout << vec[i] << ' '; cout << endl;} #define printvv(vec) rep(i, vec.size()) {rep(j, vec[i].size()) cout << vec[i][j] << ' '; cout << endl;}; #define printvvv(vec) rep(i, vec.size()) { rep(j, vec[i].size()) { rep(k, vec[i][j].size()) cout << vec[i][j][k] << ' '; cout << " "; }cout << endl; }; #define all1(x) x.begin(),x.end() #define all2(x) x.rbegin(), x.rend() #define so(x) sort(all1(x)) #define re(x) reverse(all1(x)) #define rso(x) sort(all2(x)) #define vco(x, a) count(all1(x), a) #define per(x) next_permutation(all1(x)) #define iINF 2147483647 #define llINF 9223372036854775807 #define INF 1000000000000000000 #define mod 998244353 #define mod2 1000000007 template struct Dinic{ struct Edge{ int to; T capacity; int reverse_index; }; vector> graph; vi level, iter; T inf; Dinic(int n) : graph(n), level(n), iter(n), inf(numeric_limits::max()) {} void add_edge(int from, int to, ll capacity){ graph[from].push_back({to, capacity, int(graph[to].size())}); graph[to].push_back({from, 0, int(graph[from].size()-1)}); } void bfs(int source){ level.assign(level.size(), -1); queue que; que.push(source); level[source] = 0; while(que.size()){ int v = que.front(); que.pop(); for(auto edge:graph[v]){ if(edge.capacity>0 && level[edge.to]==-1){ level[edge.to] = level[v]+1; que.push(edge.to); } } } } T dfs(int v, int sink, T flow){ if(v==sink) return flow; for(int& i = iter[v]; i0 && level[v]0){ edge.capacity -= d; graph[edge.to][edge.reverse_index].capacity += d; return d; } } } return 0; } T max_flow(int source, int sink){ T ans = 0; while(true){ bfs(source); if(level[sink]==-1) return ans; iter.assign(iter.size(), 0); while(true){ T f = dfs(source, sink, inf); if(f<=0) break; ans += f; } } } }; int main() { // アルゴリズム一覧を見る // 嘘解法ですか int n, m; cin >> n >> m; Dinic flow(n+m+2); rep(i, n){ ll a; cin >> a; flow.add_edge(i+1, n+m+1, a); } ll ans = 0; rep(i, m){ ll b; cin >> b; flow.add_edge(0, n+i+1, b); ans += b; } rep(i, m){ int k; cin >> k; rep(j, k){ ll c; cin >> c; flow.add_edge(n+i+1, c, 1e15); } } ans -= flow.max_flow(0, n+m+1); cout << ans << endl; }