题意

有一些商品和一些优惠券，每张优惠券有一定金额并且可以拆分并可以用于某些商品，问最少要付多少钱

思路

比较经典的最大流建模，把“货物”看作水流，本题中的货物指优惠券的金额，每张优惠券的金额可以“流向”特定的商品，用水流代金额的流动，每张优惠券的可用金额是源点连向优惠券的容量，商品的价格是商品到汇点的容量，然后在优惠券和可用使用的商品之间直接建容量INF边就完事了，因为有源点的容量限制，所以可以直接建INF。跑出的最大流即为最多可以使用的优惠，用总价格-最大优惠得到的就是最小支付费用。

代码

// Problem: 托米去购物
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/problem/16408
// Memory Limit: 2 MB
// Time Limit: 16408000 ms
// Time: 2022-08-29 17:33:52
// 
// Powered by CP Editor (https://cpeditor.org)

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<unordered_map>
#include<stack>
#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
#define debug(a) cout<<#a<<"="<<a<<endl;
#define sv(a,l,r,x) for(int i=l;i<=r;i++)a[i]=x;
#define pii pair <int, int>
#define endl '\n'
#define pb push_back
#define lc u<<1
#define rc u<<1|1
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
const int N=5e5+10;
int h[N],e[N],ne[N],f[N],cur[N],d[N],idx,n,m,S,T;
void add(int a,int b,int c)
{
	e[idx]=b;f[idx]=c;ne[idx]=h[a];h[a]=idx++;
	e[idx]=a;f[idx]=0;ne[idx]=h[b];h[b]=idx++;
}
bool bfs()
{
	memset(d,-1,sizeof d);
	cur[S]=h[S];d[S]=0;queue<int>q;
	q.push(S);
	while(q.size())
	{
		auto t=q.front();
		q.pop();
		for(int i=h[t];~i;i=ne[i])
		{
			int ver=e[i];
			if(d[ver]==-1&&f[i])
			{
				d[ver]=d[t]+1;
				cur[ver]=h[ver];
				if(ver==T)return true;
				q.push(ver);
			}
		}
	}
	return false;
}
int find(int u,int limit)
{
	if(u==T)return limit;
	int flow=0;
	for(int i=cur[u];~i&&flow<limit;i=ne[i])
	{
		int ver=e[i];
		cur[u]=i;
		if(d[ver]==d[u]+1&&f[i])
		{
			int t=find(ver,min(f[i],limit-flow));
			if(!t)d[ver]=-1;
			f[i]-=t;f[i^1]+=t;flow+=t;
		}
	}
	return flow;
}
int dinic()
{
	int flow,r=0;
	while(bfs())
		while(flow=find(S,INF))
			r+=flow;
	return r;
}	
void remake()
{
	idx=0;
	memset(h,-1,sizeof h);
	cin>>n>>m;
	S=0,T=m+n+1;
	int tot=0;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		tot+=x;
		add(m+i,T,x);
	}
	for(int i=1;i<=m;i++)
	{
		int x;
		cin>>x;
		add(S,i,x);
	}
	for(int i=1;i<=m;i++)
	{
		int k,x;
		cin>>k;
		while(k--)
		{
			
			cin>>x;
			add(i,m+x,INF);
		}
	}
	cout<<tot-dinic()<<endl;
}
int main()
{
     int T;
     cin>>T;
     while(T--)remake(); 	
    return 0;
}