#include <bits/stdc++.h>

using namespace std;
using LL = long long;
using PII = pair<int , int>;

const int N = 1e6 + 10 , Mod = 1e9 + 7;

int q[N];

void solved(){
    int n;
    cin >> n;

    vector<int> a(n + 1) , l(n + 1);
    vector<int> ls(n + 1);
    for(int i = 1 ; i <= n ; i ++ )
        cin >> a[i];
    int m;
    cin >> m;
    while(m -- ){
        int L , R;
        cin >> L >> R;
        l[R] = max(l[R] , L + 1);
    }

    int last = 0;
    for(int i = 1 ; i <= n ; i ++ ){
        if(l[i]) last = max(l[i] , last);
        ls[i] = last;
    }

    vector<LL> f(n + 1 , 2e18);
    f[0] = 0;
    int tt = 0 , hh = 0;
    q[0] = 0;

    for(int i = 1 ; i <= n ; i ++ ){
        if(hh <= tt && q[hh] < ls[i - 1] - 1) hh ++;

        f[i] = f[q[hh]] + a[i];
        while(hh <= tt && f[q[tt]] >= f[i]) tt --;
        q[++ tt] = i;
    }

    cout << f[n] << endl;
}

int main() {

//     freopen("D:\\dev\\code\\sunwking\\1.in" , "r" , stdin);

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    cin >> t;

    while(t -- )
        solved();

    return 0;
}