#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<string.h>
#include<set>
#include<functional>
#include<map>
#include<bitset>
#include<deque>
#include<math.h>
#include<iomanip>
#include<unordered_map>

// 我好菜啊 QAQ  

#define int ll
#define lll __int128_t
#define ST int T;scanf("%lld",&T);while(T--){ 
#define STF int T;T=read();while(T--){
#define ED }
#define foi(N) for(int i=1;i<=N;i++)
#define foj(N) for(int j=1;j<=N;j++)
#define fok(N) for(int k=1;k<=N;k++)
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define ro(i,l,r) for(int i=l;i>=r;i--)
#define YES printf("YES\n")
#define NO printf("NO\n")
#define W 64
#define CLR(Q) while(!Q.empty()) Q.pop_front();
#define lm(N) (1LL<<N)
#define FAST_IO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

typedef long long ll;

const int inf=2e18;
const int mod=998244353;

namespace FAST{
	char buf[1<<20], *p1, *p2;
	char gc() { return p1 == p2 ? p2 = buf + fread(p1 = buf, 1, 1<<20, stdin), (p1 == p2) ? EOF : *p1++ : *p1++; }
	inline int read(int f = 1, char c = gc(), int x = 0) {
		while(c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = gc();
		while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc();
		return f * x;
	}
} using FAST::read;

using namespace std;

/*
1
4
1 4 1 4
2
1 1
3 3
*/

struct sss{
	int l;
	int r;
};

struct boom{
	int p;
	int num;
};

int n;
int a[500010];
int m;
sss b[500010];
vector<int> c[500010];
int dp[500010];

signed main()
{
	STF
	
	n=read();
	foi(n) a[i]=read();
	m=read();
	foi(n){
		c[i].clear();
		c[i].push_back(inf);
	}
	foi(m){
		int l,r;
		l=read();
		r=read();
		c[r].push_back(l);
	}
	foi(n) sort(c[i].begin(),c[i].end());
	
	int cnt=0;
	int now=0;
	foi(n){
		int x=*upper_bound(c[i].begin(),c[i].end(),now);
		if(x>n) continue;
		
		b[++cnt]={x,i};
		now=x;
	}
	b[0]={0,0};
//	b[cnt+1]={n+1,n+1};
	b[cnt+1]={b[cnt].r+1,n+1};
	a[n+1]=0;
	
	deque<boom> q;
	CLR(q);
	
	int st=1;
	while(st<b[1].l) st++;
	
	int p=1;
	dp[st-1]=0;
	q.push_back({st-1,0});
	fo(i,st,n+1){
		
		if(i>b[p].r){
			while(!q.empty() && q.front().p<b[p].l) q.pop_front(); 
			fo(j,max(b[p].l,b[p-1].r+1),b[p].r){
				while(!q.empty() && q.back().num>=dp[j]) q.pop_back();
				q.push_back({j,dp[j]});
			}
			p++;
//			if(p>cnt){
//				dp[n+1]=q.front().num;
//				break;
//			}
		}
		
		
		dp[i]=q.front().num+a[i];
		
	}
	
//	foi(cnt) printf("??? %lld %lld ???\n",b[i].l,b[i].r);
//	foi(n) printf("/// %lld %lld ///\n",i,dp[i]);
	
	printf("%lld\n",dp[n+1]);
	
	ED
	
	return 0;
}