记录编号	597164	评测结果	AAWAAAAAW
题目名称	夏娜的菠萝包	最终得分	78
用户昵称	flyfree	是否通过	未通过
代码语言	C++	运行时间	0.091 s
提交时间	2024-11-25 15:29:12	内存使用	3.34 MiB

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read(){
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
ll ans,n,m,cnt;
ll t[50],d[50],lim[50];
ll sumt[50],sumd[50],_lim[50],_use[50];
struct node{
	ll d,t,lim;
};
node s[50];
bool cmp(node a,node b){
	return a.lim==b.lim?a.d<b.d:a.lim<b.lim;
}
struct bcj{
	ll f[50],siz;
	void mk(){
		memset(f,0,sizeof(f));
		for(int i=0;i<=siz;i++){
			f[i]=i;
		}
	}
	ll find(ll x){
//		cout<<x<<" "<<f[x]<<endl;
//		return f[x]==x?x:(f[x]=find(f[x]))1;
		if(f[x]==x)return x;
		else return f[x]=find(f[x]);
	}
	void merge(ll x,ll y){
		f[find(x)]=find(y);
	}
	ll re(ll x){
		ll fa=find(x);
		if(fa<=0)return -1;
		merge(fa,fa-1);
		return fa;
	}
};
ll work(ll pre){
	cnt=0;
	ll ansz=0;
	for(int i=1;i<=m;i++){
		if(pre&(1<<i-1)){
			s[++cnt]=(node){sumd[i],sumt[i],_lim[i]};				
		}
	}
	for(int i=1;i<=cnt;i++){
		s[i].lim=min(cnt,s[i].lim);
	}
	sort(s+1,s+1+cnt,cmp);
	bcj k;
	k.siz=cnt;
	k.mk();
	for(int i=1;i<=cnt;i++){
		ll now=k.re(s[i].lim);
//		cout<<s[i].t<<" "<<s[i].d<<" "<<s[i].lim<<" "<<now<<endl;
		if(now==-1)return -1;
		ansz+=s[i].t-s[i].d*(now-1);
	}
	return ansz;
}
void dfs(ll i,ll used,ll pre){
	if(i>m){
		ans=max(ans,work(pre));
		return;
	}
	if(!(used&_use[i]))dfs(i+1,used|_use[i],pre|(1<<i-1));
	dfs(i+1,used,pre);
}
int main(){
	freopen("shana.in","r",stdin);
	freopen("shana.out","w",stdout);
	while(1){
		n=read(),ans=0;
		if(!n)break;
		for(int i=1;i<=n;i++){
			t[i]=read(),d[i]=read();
			lim[i]=(t[i])/d[i]+1;
		}
		m=read();
		for(int i=1;i<=m;i++){
			ll k=read(),e=read();
			sumt[i]=e,sumd[i]=0,_lim[i]=1e9,_use[i]=0;
			for(int j=1;j<=k;j++){
				ll p=read();
				sumt[i]+=t[p],sumd[i]+=d[p];
				_lim[i]=min(_lim[i],lim[p]);
				_use[i]|=(1<<p-1);
			}
		}
		dfs(1,0,0);
		cout<<ans<<endl;
	}
	return 0;
}