#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int,int>

const int N = 1e5 + 7;
int a[N];
struct Station{
    int x = 0, t;
    bool operator<(const Station &other){
        return x < other.x;
    }
}s[N];

void solve()
{
    int n, m;
    cin>>n>>m;
    vector<vector<int> > bind(n+1);
    vector<int> use(n+1);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=m;i++)
    {
        cin>>s[i].x>>s[i].t;
    }
    sort(s+1, s+m+1);
    for(int i=1;i<=m;i++)
    {
        bind[s[i].t].push_back(i);
    }
    ll fre = 0;
    priority_queue<pii, vector<pii>, greater<pii> > pq;
    for(int i=1;i<=n;i++)
    {
        if(bind[i].size()==0) {
            fre += a[i];
        }else {
            pq.push({bind[i][0], a[i]});
            use[i]++;
        }
    }
    ll bet = 0;
    for(int i=1;i<=m;i++)
    {  
        int dis = s[i].x - s[i-1].x;
        while(pq.size() && dis)
        {
            auto [sid, c] = pq.top();
            pq.pop();
            if(dis>=c) {
                dis -= c;
            }else {
                dis = 0;
                c -= dis;
                pq.push({sid, c});
            }
        }
        if(dis) {
            if(dis > fre) {
                cout<<s[i].x - (dis-fre);
                return;
            }else{
                fre -= dis;
            }
        }
        if(pq.size()) {
            auto [sid, c] = pq.top();
            if(sid==i) {
                pq.pop();
            }
            int bid = s[i].t;
            if(use[bid] < bind[bid].size()) {
                pq.push({bind[bid][use[bid]], a[bid]});
                use[bid]++;
            } else {
                fre += a[bid];
            }
        }
        else {
            int bid = s[i].t;
            if(use[bid] < bind[bid].size()) {
                pq.push({bind[bid][use[bid]], a[bid]});
                use[bid]++;
            } else {
                fre += a[bid];
            }
        }
    }
    cout<<s[m].x + fre<<endl;
}
signed main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int T = 1;
    cin>>T;
    while (T--) solve();
    return 0;
}