#include <bits/stdc++.h>
#define int 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],to[N],nxt[N],f[N],tmphead[N],c[N],cnt=-1;
	int maxflow,mincost;
	void add(int u,int v,int fl,int w){
		++cnt;
		nxt[cnt]=head[u];
		head[u]=cnt;to[cnt]=v;
		f[cnt]=fl;c[cnt]=w;
		++cnt;
		nxt[cnt]=head[v];
		head[v]=cnt;to[cnt]=u;
		f[cnt]=0;c[cnt]=-w;
	}
	int dis[N],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]=1e9,vis[i]=0;
		q.push(s);vis[s]=1;dis[s]=0;
		int cur=0;
		while(q.size()){
			int u;
			if(cur==0){
				u=q.a[q.head++];
			}else u=q.a[q.tail--];
			vis[u]=0;
			for(int i=head[u];~i;i=nxt[i]){
				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];
	void solve(){
		while(true){
			int tmp=cnt;
			for(int i=0;i<=n;i++)tmphead[i]=head[i];
			for(int i=1;i<=::n;i++){
				if(P[i].size())add(s,i,1,P[i].back()),pid[i]=cnt;
				if(Q[i].size())add(i,t,1,Q[i].back()),qid[i]=cnt;
			}
			SPFA();
			if(dis[t]==1e9)return;
			int minf=1e9,sumc=0,now=t;
			vector <int> path;
			while(now!=s){
				path.push_back(pre[now][1]);
				minf=min(minf,f[pre[now][1]]);
				sumc+=c[pre[now][1]];
				now=pre[now][0];
			}
			for(int i=0;i<path.size();i++){
				f[path[i]]-=minf;
				f[path[i]^1]+=minf;
			}
			for(int i=1;i<=::n;i++){
				if(P[i].size()&&f[pid[i]])P[i].pop_back();
				if(Q[i].size()&&f[qid[i]])Q[i].pop_back();
			}
			cnt=tmp;
			for(int i=0;i<=n;i++)head[i]=tmphead[i];
			mincost+=minf*sumc;
			cout<<mincost<<"\n";
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	memset(MCMF::head,-1,sizeof(MCMF::head));
	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());
	}
	MCMF::solve();
	cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
	return 0;
}