#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a),i##END=(b);i<=i##END;i++)
#define Rof(i,b,a) for(int i=(b),i##END=(a);i>=i##END;i--)
#define go(u) for(int i=head[u];i;i=nxt[i])
#define ll long long
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
const int N=810,M=5e4+10; 
int n,m,d[N],cnt[N];
vector<int> A[N],B[N];
ll ans;
signed main(){
	n=read(),m=read();For(i,1,n-1)d[i]=read();
	For(i,1,m){int x=read(),y=read();A[x].push_back(y);}
	For(i,1,m){int x=read(),y=read();B[x].push_back(y);}
	For(i,1,n)sort(A[i].begin(),A[i].end(),greater<int>());
	For(i,1,n)sort(B[i].begin(),B[i].end(),greater<int>());
	while(m--){
		int W=1e9,X=0,Y=0;
		int id=0,sum=1e9;
		For(i,1,n){
			if(i>1)sum+=cnt[i-1]>=0?d[i-1]:-d[i-1];
			if(!A[i].empty()&&A[i].back()<sum)sum=A[i].back(),id=i;
			if(!B[i].empty()&&sum+B[i].back()<W)W=sum+B[i].back(),X=id,Y=i;
		}id=0,sum=1e9;
		Rof(i,n,1){
			if(i<n)sum+=cnt[i]<=0?d[i]:-d[i];
			if(!A[i].empty()&&A[i].back()<sum)sum=A[i].back(),id=i;
			if(!B[i].empty()&&sum+B[i].back()<W)W=sum+B[i].back(),X=id,Y=i;
		}ans+=W;
		A[X].pop_back(),B[Y].pop_back();
		if(X<Y)For(i,X,Y-1)cnt[i]++;
		else Rof(i,X-1,Y)cnt[i]--;
		printf("%lld\n",ans);
	}
	return 0;
}