#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,pre[i][0]=pre[i][1]=0;
		q.push(s);vis[s]=1;dis[s]=0;
		while(q.size()){
			int u=q.front();q.pop();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(auto it:path){
				f[it]-=minf;
				f[it^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;
}

answer.code: In function ‘void MCMF::solve()’:
answer.code:69:34: error: ‘it’ does not name a type; did you mean ‘int’?
   69 |                         for(auto it:path){
      |                                  ^~
      |                                  int
answer.code:72:26: error: expected ‘;’ before ‘for’
   72 |                         }
      |                          ^
      |                          ;
   73 |                         for(int i=1;i<=::n;i++){
      |                         ~~~
answer.code:73:25: error: expected primary-expression before ‘for’
   73 |                         for(int i=1;i<=::n;i++){
      |                         ^~~
answer.code:72:26: error: expected ‘;’ before ‘for’
   72 |                         }
      |                          ^
      |                          ;
   73 |                         for(int i=1;i<=::n;i++){
      |                         ~~~
answer.code:73:25: error: expected primary-expression before ‘for’
   73 |                         for(int i=1;i<=::n;i++){
      |                         ^~~
answer.code:72:26: error: expected ‘)’ before ‘for’
   72 |                         }
      |                          ^
      |                          )
   73 |                         for(int i=1;i<=::n;i++){
      |                         ~~~
answer.code:69:28: note: to match this ‘(’
   69 |                         for(auto it:path){
      |                            ^