记录编号	98471	评测结果	AAAAAAAAAA
题目名称	电子书狂热者	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	0.557 s
提交时间	2014-04-23 14:07:51	内存使用	0.62 MiB

#include<fstream>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const long long SIZEN=1010,SIZES=10010,INF=0x7FFFFFFF;
long long N,N1,N2,N3;
long long book=0;
long long book_sum[SIZES];
long long origin_cost[SIZES],origin_sum[SIZEN];
long long benefit1[SIZES],benefit2[SIZEN];
long long a[SIZEN],b[SIZEN],c[SIZEN],d[SIZEN],p[SIZEN],r[SIZEN],s[SIZEN];
void package_1(long long n)
{
	benefit1[0]=0;
	for(long long i=1;i<SIZES;i++)
		benefit1[i]=INF;
	for(long long i=1;i<=n;i++)
	{
		benefit1[a[i]]=min(benefit1[a[i]],r[i]);
		long long temp=a[i]-1;
		while(temp>0 && benefit1[temp]>benefit1[a[i]])
			benefit1[temp]=benefit1[a[i]],temp--;
		for(long long j=1;j<=book-a[i];j++)
		{
			if(benefit1[j+a[i]]<benefit1[j]+r[i])continue;
			benefit1[j+a[i]]=benefit1[j]+r[i];
			temp=j+a[i]-1;
			while(temp>0 && benefit1[temp]>benefit1[j+a[i]])
				benefit1[temp]=benefit1[j+a[i]],temp--;
		}
	}
}
void package_2(long long n)
{
	benefit2[0]=0;
	for(long long i=1;i<SIZEN;i++)
		benefit2[i]=INF;
	for(long long i=1;i<=n;i++)
	{
		benefit2[b[i]]=min(benefit2[b[i]],s[i]);
		long long temp=b[i]-1;
		while(temp>0 && benefit2[temp]>benefit2[b[i]])
			benefit2[temp]=benefit2[b[i]],temp--;
		for(long long j=1;j<=N-b[i];j++)
		{
			if(benefit2[j+b[i]]<benefit2[j]+s[i])continue;
			benefit2[j+b[i]]=benefit2[j]+s[i];
			temp=j+b[i];
			while(temp>0 && benefit2[temp]>benefit2[j+b[i]])
				benefit2[temp]=benefit2[j+b[i]],temp--;
		}
	}
}
long long F[SIZEN];
void work()
{
	for(long long i=0;i<N;i++)
	{
		for(long long j=i+1;j<=N;j++)
		{
			F[j]=min(F[j],F[i]+benefit1[book_sum[j]-book_sum[i]]);//套餐1中获利
			F[j]=min(F[j],F[i]+benefit2[j-i]);//套餐2中获利
			F[j]=min(F[j],F[i]+(origin_sum[j]-origin_sum[i]));//从原价获利
		}
	}
	printf("%lld\n",F[N]);
}
int main()
{
	freopen("zealot.in","r",stdin);
	freopen("zealot.out","w",stdout);
	scanf("%lld",&N);
	while(N)
	{
		book=0;
		book_sum[0]=0;
		for(long long i=1;i<=N;i++)
		{
			scanf("%lld",&d[i]);
			book+=d[i];
			book_sum[i]=book_sum[i-1]+d[i];
		}
		//====================================================================================
		scanf("%lld",&N1);
		for(long long i=1;i<=N1;i++)
		{
			scanf("%lld %lld",&c[i],&p[i]);
		}
		F[0]=0;
		long long temp=1,cost;
		for(long long i=1;i<=N;i++)
		{
			if(temp<=N1 && c[temp]==i)
			{
				cost=p[temp];
				temp++;
			}
			F[i]=F[i-1]+cost*d[i];//原价
			origin_sum[i]=F[i];
		}
		//====================================================================================
		scanf("%lld",&N2);
		for(long long i=1;i<=N2;i++)
		{
			scanf("%lld %lld",&a[i],&r[i]);
		}
		package_1(N2);
		//====================================================================================
		scanf("%lld",&N3);
		for(long long i=1;i<=N3;i++)
		{
			scanf("%lld %lld",&b[i],&s[i]);
		}
		package_2(N3);
		work();
		scanf("%lld",&N);
	}
	return 0;
}