#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <map>
#include <set>
using namespace std;
using ll=long long;
const int maxn=1e6+5;
const ll mod=1e9+7;
ll b[maxn],bmx[maxn];
pair<ll,ll> pos[maxn];
void solve() {
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        cin>>b[i];
        bmx[i]=b[i];
    }
    queue<ll> q[n+1];
    for(int i=1;i<=m;i++) {
        cin>>pos[i].first>>pos[i].second;
        q[pos[i].second].push(pos[i].first);
    }
    ll sum=0;
    priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<>> pq;
    for(int i=1;i<=n;i++) {
        sum+=b[i];
        if(!q[i].empty()) {
            pq.push({q[i].front(),i});
            q[i].pop();
        }
    }
    ll last=0;
    pos[m+1]={1e18,0};
    for(int now=1;now<=m+1;now++) {
        ll d=pos[now].first-last;
        if(d>sum) {
            cout<<last+sum<<"\n";
            return;
        }
        while (!pq.empty()&&pq.top().first<now) {
            pair<ll,ll> p=pq.top();
            pq.pop();
            if(!q[p.second].empty()) {
                pq.push({q[p.second].front(),p.second});
                q[p.second].pop();
            }
        }
        sum-=d;
        while (d) {
            if(pq.empty()) break;
            pair<ll,ll> p=pq.top();
            pq.pop();
            ll tmp=min(d,b[p.second]);
            d-=tmp;
            b[p.second]-=tmp;
            if(b[p.second]) pq.push(p);
        }
        if(b[pos[now].second]==0&&!q[pos[now].second].empty()) {
            pq.push({q[pos[now].second].front(),pos[now].second});
            q[pos[now].second].pop();
        }
        sum+=bmx[pos[now].second]-b[pos[now].second];
        b[pos[now].second]=bmx[pos[now].second];
        last=pos[now].first;
    }
    
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    cin>>t;
    while (t--) {
        solve();
    }
    return 0;
}