#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
using LL=long long;
const int inf=0x3f3f3f3f;
#define ll long long
#define N 805
#define M 50005
int d[N],n,m;
vector<int> wa[N],wb[N];
int cnt[N];
int main(){
#ifdef xay5421
	freopen("a.in","r",stdin);
#endif
	cin>>n>>m;
	for(int i=1;i<n;i++) scanf("%d",&d[i]);
	for(int i=1;i<=m;i++)
	{
		int pos,w; scanf("%d %d",&pos,&w);
		wa[pos].push_back(w);
	}
	for(int i=1;i<=n;i++) sort(wa[i].begin(),wa[i].end(),greater<int>());
	for(int i=1;i<=m;i++)
	{
		int pos,w; scanf("%d %d",&pos,&w);
		wb[pos].push_back(w);
	}
	for(int i=1;i<=n;i++) sort(wb[i].begin(),wb[i].end(),greater<int>());
	ll ans=0;
	for(int _=1;_<=m;_++)
	{
		int mnw=inf;
		int mnx=0,mny=0;
		int preid=0,presum=inf;
		for(int i=1;i<=n;i++)
		{
			if(i!=1) presum+=cnt[i-1]>=0?d[i-1]:-d[i-1];
			if(!wa[i].empty())
			{
				if(presum>wa[i].back()) presum=wa[i].back(),preid=i;
			}
			if(!wb[i].empty())
			{
				int nw=presum+wb[i].back();
				if(nw<mnw) mnw=nw,mnx=preid,mny=i;
			}
		}
		preid=0,presum=inf;
		for(int i=n;i>=1;i--)
		{
			if(i!=n) presum+=cnt[i]<=0?d[i]:-d[i];
			if(!wa[i].empty())
			{
				if(presum>wa[i].back()) presum=wa[i].back(),preid=i;
			}
			if(!wb[i].empty())
			{
				int nw=presum+wb[i].back();
				if(nw<mnw) mnw=nw,mnx=preid,mny=i;
			}
		}
//		printf("%d %d %d\n",mnx,mny,mnw);
		assert(mnx!=0&&mny!=0);
		ans+=mnw;
		wa[mnx].pop_back(),wb[mny].pop_back();
		if(mnx<mny)
		{
			for(int i=mnx;i<mny;i++) cnt[i]++;
		}
		else
		{
			for(int i=mny;i<mnx;i++) cnt[i]--;
		}
		printf("%lld\n",ans);
	}
	return 0;
}