1 /**************************************************************  2     Problem: 3438  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:2664 ms  7     Memory:24280 kb  8 ****************************************************************/  9   10 #include <cstdio> 11 #include <cstring> 12 #include <algorithm> 13   14 using namespace std; 15 const int inf = (int) 1e9; 16 const int N = 3005; 17 const int M = 2000005; 18   19 struct edges{ 20     int next, to, f; 21     edges() {} 22     edges(int _n, int _t, int _f) : next(_n), to(_t), f(_f) {} 23 } e[M]; 24   25 int n, m; 26 int cnt, ans, S, T; 27 int first[N], tot = 1; 28 int q[N], d[N]; 29   30 inline int read() { 31     int x = 0; 32     char ch = getchar(); 33     while (ch < ‘0‘ || ‘9‘ < ch) 34         ch = getchar(); 35     while (‘0‘ <= ch && ch <= ‘9‘) { 36         x = x * 10 + ch - ‘0‘; 37         ch = getchar(); 38     } 39     return x; 40 } 41   42 inline void Add_Edges(int x, int y, int z){ 43     e[++tot] = edges(first[x], y, z), first[x] = tot; 44     e[++tot] = edges(first[y], x, 0), first[y] = tot; 45 } 46     47 bool bfs(){ 48     memset(d, 0, sizeof(d)); 49     q[1] = S, d[S] = 1; 50     int l = 0, r = 1, x, y; 51     while (l < r){ 52         ++l; 53         for (x = first[q[l]]; x; x = e[x].next){ 54             y = e[x].to; 55             if (!d[y] && e[x].f) 56                 q[++r] = y, d[y] = d[q[l]] + 1; 57         } 58     } 59     return d[T]; 60 } 61     62 int dinic(int p, int limit){ 63     if (p == T || !limit) return limit; 64     int x, y, tmp, rest = limit; 65     for (x = first[p]; x; x = e[x].next){ 66         y = e[x].to; 67         if (d[y] == d[p] + 1 && e[x].f && rest){ 68             tmp = dinic(y, min(rest, e[x].f)); 69             rest -= tmp; 70             e[x].f -= tmp, e[x ^ 1].f += tmp; 71             if (!rest) return limit; 72         } 73     } 74     if (limit == rest) d[p] = 0; 75     return limit - rest; 76 } 77     78 int Dinic(){ 79     int res = 0, x; 80     while (bfs()) 81         res += dinic(S, inf); 82     return res; 83 } 84   85 int main() { 86     int i, j, x, y, z; 87     n = cnt = read(), S = 3001, T = 3002; 88     for (i = 1; i <= n; ++i) { 89         ans += (x = read()); 90         Add_Edges(S, i, x); 91     } 92     for (i = 1; i <= n; ++i) { 93         ans += (x = read()); 94         Add_Edges(i, T, x); 95     } 96     m = read(); 97     for (i = 1; i <= m; ++i) { 98         j = read(), x = read(), y = read(); 99         ans += x + y;100         Add_Edges(S, ++cnt, x), Add_Edges(++cnt, T, y);101         while (j--) {102             z = read();103             Add_Edges(z, cnt, inf), Add_Edges(cnt - 1, z, inf);104         }105     }106     printf("%d\n", ans - Dinic());107     return 0;108 }