#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e4+10;
vector <int> P[N],Q[N];
int n,m,dis[N],a[N],b[N],c[N],d[N];
namespace MCMF{
	const int N=1e6+10;
	int n,s,t,head[N],from[N],to[N],nxt[N],lst[N],f[N],tmphead[N],c[N],cnt=-1;
	ll maxflow,mincost;
	void add(int u,int v,int fl,int w){
		++cnt;
		if(head[u]!=-1)lst[head[u]]=cnt;
		nxt[cnt]=head[u];from[cnt]=u;
		head[u]=cnt;to[cnt]=v;
		f[cnt]=fl;c[cnt]=w;
		++cnt;
		if(head[v]!=-1)lst[head[v]]=cnt;
		nxt[cnt]=head[v];from[cnt]=v;
		head[v]=cnt;to[cnt]=u;
		f[cnt]=0;c[cnt]=-w;
	}
	void del(int id){
		if(nxt[id]!=-1){
			if(lst[id]!=-1){
				lst[nxt[id]]=lst[id];
				nxt[lst[id]]=nxt[id];
			}
			else head[from[id]]=nxt[id],lst[nxt[id]]=-1;
		}else{
			if(lst[id]!=-1)nxt[lst[id]]=-1;
			else head[from[id]]=-1;
		}
	}
	ll dis[N];int vis[N],pre[N][2];
	struct Queue{
		int head,tail,a[N];
		void push(int x){a[++tail]=x;}
		void pop(){++head;}
		int size(){return tail-head+1;}
		int front(){return a[head];}
	}q;
	void SPFA(){
		q.head=q.tail=0;
		for(int i=0;i<=n;i++)dis[i]=1e18,vis[i]=0;
		q.push(s);vis[s]=1;dis[s]=0;
		int cur=0;
		while(q.size()){
			int u=q.front();q.pop();
			cur^=1;
			vis[u]=0;
			for(int i=head[u];~i;i=nxt[i]){
				//cerr<<u<<" "<<i<<endl;
				int v=to[i],w=c[i];
				if(!f[i])continue;
				if(dis[v]>dis[u]+w){
					dis[v]=dis[u]+w;
					pre[v][0]=u;
					pre[v][1]=i;
					if(!vis[v]){
						q.push(v);vis[v]=1;
					}
				}
			}
		}	
	}
	int pid[N],qid[N],path[N],Test,Tsum;
	void solve(){
		while(true){
			//cerr<<(++Test)<<endl;
			//auto bg=clock();
			SPFA();
			//auto ed=clock();
			//Tsum+=ed-bg;
			if(dis[t]==1e18)break;
			ll minf=1e9,sumc=0;int now=t;
			int psz=0;
			while(now!=s){
				path[psz++]=pre[now][1];
				minf=min(minf,1ll*f[pre[now][1]]);
				sumc+=c[pre[now][1]];
				now=pre[now][0];
			}
			for(int i=0;i<psz;i++){
				f[path[i]]-=minf;
				f[path[i]^1]+=minf;
			}
			for(int i=1;i<=::n;i++){
				if(P[i].size()&&f[pid[i]]){
					del(pid[i]);del(pid[i]^1);
					P[i].pop_back();
					if(P[i].size()){
						add(s,i,1,P[i].back()),pid[i]=cnt;
					}
				}
				if(Q[i].size()&&f[qid[i]]){
					del(qid[i]);del(qid[i]^1);
					Q[i].pop_back();
					if(Q[i].size()){
						add(i,t,1,Q[i].back()),qid[i]=cnt;
					}
				}
			}
			//cerr<<minf<<" "<<cnt<<endl;
			mincost+=1ll*minf*sumc;
			cout<<mincost<<"\n";
		}
		//cerr<<1.0*Tsum/CLOCKS_PER_SEC<<endl;
	}
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	memset(MCMF::head,-1,sizeof(MCMF::head));
	memset(MCMF::lst,-1,sizeof(MCMF::lst));
	cin>>n>>m;
	for(int i=1;i<n;i++)cin>>dis[i];
	for(int i=1;i<=m;i++)cin>>a[i]>>b[i];
	for(int i=1;i<=m;i++)cin>>c[i]>>d[i];
	MCMF::t=n+1;MCMF::s=0;MCMF::n=MCMF::t;
	for(int i=1;i<n;i++){
		MCMF::add(i,i+1,1e9,dis[i]);
		MCMF::add(i+1,i,1e9,dis[i]);
	}
	for(int i=1;i<=m;i++)
		Q[a[i]].push_back(b[i]);
	for(int i=1;i<=m;i++)
		P[c[i]].push_back(d[i]);
	for(int i=1;i<=n;i++){
		sort(Q[i].begin(),Q[i].end());
		sort(P[i].begin(),P[i].end());
		reverse(Q[i].begin(),Q[i].end());
		reverse(P[i].begin(),P[i].end());
	}
	for(int i=1;i<=n;i++){
		if(P[i].size())MCMF::add(MCMF::s,i,1,P[i].back()),MCMF::pid[i]=MCMF::cnt;
		if(Q[i].size())MCMF::add(i,MCMF::t,1,Q[i].back()),MCMF::qid[i]=MCMF::cnt;
	}
	MCMF::solve();
	cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
	return 0;
}