记录编号	597238	评测结果	AAAAAAAAA
题目名称	夏娜的菠萝包	最终得分	100
用户昵称	黄天宇	是否通过	通过
代码语言	C++	运行时间	0.423 s
提交时间	2024-11-25 19:59:25	内存使用	6.49 MiB

#include<bits/stdc++.h>
using namespace std;
int T;
int n,m;
const int MAXN=105; 
struct edge{
	int v;
	int d;
}e[MAXN];
int sum[MAXN];
int t[MAXN];
int de[MAXN];
int E[MAXN];
int k[MAXN];
int s[MAXN];
int v[MAXN][MAXN];
int p[MAXN];
int maxx;
int f[(1<<15)+5][25];
int main(){
	freopen("shana.in","r",stdin);
	freopen("shana.out","w",stdout);
	while(cin>>n){
		if(n==0) break;
		p[0]=1;
		for(int i=1;i<=n;i++){
			p[i]=p[i-1]*2;
		}
		memset(t,0x3f,sizeof(t));
		memset(de,0,sizeof(de));
		memset(sum,0,sizeof(sum));
		memset(f,0,sizeof(f));
		memset(s,0,sizeof(s));
		for(int i=1;i<=n;i++){
			cin>>e[i].v>>e[i].d;
		}
		cin>>m;
		for(int i=1;i<=m;i++){
			cin>>k[i]>>E[i];
			for(int j=1;j<=k[i];j++){
				int num;
				cin>>num;
				s[i]+=p[num-1];
				sum[i]+=e[num].v;
				de[i]+=e[num].d;
				t[i]=min(t[i],e[num].v/e[num].d+1);
			}
			sum[i]+=E[i];
		}
		for(int i=1;i<=m;i++){
			for(int j=1;j<=n;j++){
				if(j>t[i]) v[i][j]=-1061109567;
				else
				v[i][j]=sum[i]-de[i]*(j-1);
			}
		}
		for(int i=1;i<=p[n]-1;i++){
			for(int j=1;j<=n;j++){
				for(int h=1;h<=m;h++){
					if((i&s[h])==s[h]){
						f[i][j]=max(max(f[i][j],f[i][j-1]),f[(i-s[h])][j-1]+v[h][j]);
					} 
				}
			}
		}
		for(int i=1;i<=p[n]-1;i++){
			maxx=max(maxx,f[i][n]);
		}
		cout<<maxx<<endl;
		maxx=0;
	}

	return 0;
}