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

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
const int SIZEN=2010,SIZES=20010;
const ll INF=1e18;
int N;
ll booknum[SIZEN];
ll readsum[SIZEN];
ll price[SIZEN];
int n2;//第一种套餐
ll A[SIZEN],R[SIZEN];
//连续A[i]本交R[i]
ll booksum;//读书总数
ll conw[SIZES]={0};
int n3;//第二种套餐
ll B[SIZEN],S[SIZEN];
//连续B[i]天交S[i]
ll f[SIZEN];
void preDP(void){
	for(int i=0;i<=booksum;i++) conw[i]=INF;
	conw[0]=0;
	for(int i=1;i<=n2;i++){
		//这个套餐:连续A[i]本交R[i]
		for(int j=A[i];j>=0;j--) conw[j]=min(conw[j],R[i]);
	}
	for(int i=1;i<=booksum;i++){
		for(int j=1;j*2<=i;j++){
			conw[i]=min(conw[i],conw[j]+conw[i-j]);
		}
	}
}
void work(void){
	f[0]=0;
	for(int i=1;i<=N;i++){
		f[i]=f[i-1]+booknum[i]*price[i];
		for(int j=0;j<i;j++) f[i]=min(f[i],f[j]+conw[readsum[i]-readsum[j]]);//最后用了若干次第一种套餐,j是上一个"完整的天"
		for(int j=1;j<=n3;j++){
			int temp=(i-B[j]>=0)?i-B[j]:0;
			f[i]=min(f[i],f[temp]+S[j]);//最后用了第二种套餐,j是用的套餐编号
		}
		//这个套餐是连续B[j]天交S[j]
	}
	printf("%lld\n",f[N]);
}
void setzero(ll s[SIZEN]){
	for(int i=0;i<SIZEN;i++) s[i]=0;
}
bool read(void){
	scanf("%d",&N);
	if(!N) return false;
	setzero(booknum);
	setzero(readsum);
	setzero(price);
	setzero(A);
	setzero(R);
	setzero(conw);
	for(int i=0;i<SIZES;i++) conw[i]=0;
	setzero(B);
	setzero(S);
	setzero(f);
	booksum=0;
	readsum[0]=0;
	for(int i=1;i<=N;i++){
		cin>>booknum[i];
		booksum+=booknum[i],readsum[i]=readsum[i-1]+booknum[i];
	}
	int n1;
	scanf("%d",&n1);
	int last=0,c;
	ll p;
	for(int i=1;i<=n1;i++){
		cin>>c>>p;
		for(int j=last;j<c;j++) price[j]=price[last];
		price[c]=p;
		last=c;
	}
	for(int j=last;j<=N;j++) price[j]=price[last];
	scanf("%d",&n2);
	for(int i=1;i<=n2;i++) scanf("%lld%lld",&A[i],&R[i]);
	scanf("%d",&n3);
	for(int i=1;i<=n3;i++) scanf("%lld%lld",&B[i],&S[i]);
	return true;
}
int main(){
	freopen("zealot.in","r",stdin);
	freopen("zealot.out","w",stdout);
	while(read()){
		preDP();
		work();
	}
	return 0;
}