#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define int long long
int solve()
{
    int n;
    cin >> n;
    map<int, int> t;
    vector<int> a(n + 2);
    vector<int> dp(n + 2);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    int q;
    cin >> q;
    t[0] = 0;
    for (int i = 0; i < q; i++)
    {
        int l, r;
        cin >> l >> r;
        t[r] = max(t[r], l);
    }
    queue<pair<int, int>> tmp;
    for (auto it : t)
    {
        tmp.emplace(it);
    }
    tmp.push({998244353, 0});
    list<int> p;
    p.emplace_back(0);
    int l = 0;
    for (int i = 1; i <= n + 1; i++)
    {
        while (p.front() < l)
        {
            p.pop_front();
        }
        dp[i] = a[i] + dp[p.front()];
        while (!p.empty() && dp[p.back()] >= dp[i])
        {
            p.pop_back();
        }
        p.push_back(i);
        if (i >= tmp.front().first)
        {
            l = max(l, tmp.front().second);
            tmp.pop();
        }
    }
    cout << dp[n + 1] << "\n";
    return 0;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int test = 1;
    cin >> test;
    while (test--)
    {
        solve();
    }

    return 0;
}