Description

小 M 还是个特么喜欢玩 MC 的孩纸......

小 M 在 MC 里开辟了两块巨大的耕地 \(A\) 和 \(B\) (你可以认为容量是无穷), 现在, 小 P 有 \(n\) 种作物的种子, 每种作物的种子有 \(1\) 个 (就是可以种一棵作物, 用 \(1 \ldots n\) 编号), 现在, 第 \(i\) 种作物种植在 \(A\) 中种植可以获得 \(a_i\) 的收益, 在 \(B\) 中种植可以获得 \(b_i\) 的收益. 而且, 现在还有这么一种神奇的现象, 就是某些作物共同种在一块耕地中可以获得额外的收益, 小 M 找到了规则中共有 \(m\) 种作物组合, 第 \(i\) 个组合中的作物共同种在 \(A\) 中可以获得 \(c_{1,i}\) 的额外收益, 共同种在 \(B\) 中可以获得 \(c_{2,i}\) 的额外收益, 所以, 小 M 很快的算出了种植的最大收益, 但是他想要考考你, 你能回答他这个问题么?

Input

第一行包括一个整数 \(n\);

第二行包括 \(n\) 个整数, 表示 \(a_i\);

第三行包括 \(n\) 个整数, 表示 \(b_i\);

第四行包括一个整数 \(m\);

接下来 \(m\) 行, 对于接下来的第 \(i\) 行: 第一个整数 \(k_i\), 表示第 \(i\) 个作物组合中 共有 \(k_i\) 种作物, 接下来两个整数 \(c_{1,i}, c_{2,i}\), 接下来 \(k_i\) 个整数, 表示 该组合中的作物编号.

Output

只有一行, 包括一个整数, 表示最大收益

Sample Input

3
4 2 1
2 3 2
1
2 3 2 1 2

Sample Output

11

Data Range

对于 100% 的数据,\(1 \leq k \lt n \leq 1000, 0 \lt m \leq 1000\), 且保证所有数据及结果不超过 \(2 \times 10^9\).

Explanation

一看就知道两个农田应该用最小割......

建图就不用说了吧, 经典最小割模型~

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>

using namespace std;
typedef long long lli;
const int maxn = 4010, maxm = 4000100;
const lli infinit = 0x007f7f7f7f7f7f7fll;

class Dinic
{
public:
    struct edge {
        int u, v;
        lli flow;
        edge *next, *rev;
    };
    int n, s, t, ecnt;
    edge *edges[maxn], epool[maxm];
    int level[maxn];
    void add_edge(int u, int v, lli flow)
    {
        edge *p = &epool[++ecnt],
             *q = &epool[++ecnt];
        p->u = u; p->v = v; p->flow = flow;
        p->next = edges[u]; edges[u] = p;
        q->u = v; q->v = u; q->flow = 0;
        q->next = edges[v]; edges[v] = q;
        p->rev = q; q->rev = p;
        return ;
    }
    bool make_level(void)
    {
        for (int i = 1; i <= n; i++)
            level[i] = 0;
        queue<int> que;
        que.push(s);
        level[s] = 1;
        while (!que.empty()) {
            int p = que.front();
            que.pop();
            for (edge *ep = edges[p]; ep; ep = ep->next)
                if (ep->flow && !level[ep->v]) {
                    level[ep->v] = level[p] + 1;
                    que.push(ep->v);
                }
        }
        if (level[t] <= 0)
            return false;
        return true;
    }
    lli dfs(int p, lli mn)
    {
        if (p == t)
            return mn;
        lli sum = 0, tmp;
        for (edge *ep = edges[p]; ep && sum < mn; ep = ep->next)
            if (ep->flow && level[ep->v] == level[p] + 1) {
                tmp = dfs(ep->v, min(mn - sum, ep->flow));
                if (tmp > 0) {
                    ep->flow -= tmp;
                    ep->rev->flow += tmp;
                    sum += tmp;
                }
            }
        if (sum < mn)
            level[p] = 0;
        return sum;
    }
    lli eval(void)
    {
        lli sum = 0, tmp;
        while (make_level()) {
            tmp = dfs(s, infinit);
            if (tmp <= 0)
                break;
            sum += tmp;
        }
        return sum;
    }
} graph;

int n, m;
int a[maxn], b[maxn];

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
        scanf("%d", &b[i]);
    scanf("%d", &m);
    graph.n = n + 2*m + 2;
    graph.s = graph.n - 1;
    graph.t = graph.n;
    lli res = 0;
    for (int i = 1; i <= n; i++) {
        graph.add_edge(graph.s, i, b[i]);
        graph.add_edge(i, graph.t, a[i]);
        res += a[i] + b[i];
    }
    for (int i = 1; i <= m; i++) {
        int k, c1, c2, x;
        scanf("%d%d%d", &k, &c1, &c2);
        graph.add_edge(graph.s, n+i*2, c2);
        graph.add_edge(n+i*2-1, graph.t, c1);
        res += c1 + c2;
        for (int j = 1; j <= k; j++) {
            scanf("%d", &x);
            graph.add_edge(x, n+i*2-1, infinit);
            graph.add_edge(n+i*2, x, infinit);
        }
    }
    res -= graph.eval();
    printf("%lld\n", res);
    return 0;
}