#include<bits/stdc++.h>
#define forn(u,n) for(int u=0;u<n;++u)
#define forns(u,i,n) for(int u=i;u<n;++u)
#define reverso
#define pb push_back
#define all(a) a.begin(), a.end()
#define snd second
#define fst first

using namespace std;

typedef long long ll;
int main(){
    #ifdef LOCAL
        freopen("entra.in","r",stdin);
    #endif // LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        queue<ll>place[n+2];//PARA CADA BATERIA TIENE ORDENADO DISTANCIA DE LA MAS CERCANA
        vector<ll>battery(n+1,0);//ACTUALMENTE PARA DEL TIPO I HAY battery_i
        vector<ll>tope(n+1,0);//ACTUALMENTE PARA DEL TIPO I HAY battery_i
        forns(i,1,n+1){
            cin>>battery[i];
            tope[i]=battery[i];
        }
        vector<pair<ll,ll>>charge;//ORDENA LA GASOLINERAS
        priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>>prioridad; // DE CUAL BATERIA TOMAR
        forn(i,m){
            ll x;
            int type;
            cin>>x>>type;
            charge.pb({x,type});
        }
        sort(all(charge));
        for(auto it:charge){
            place[it.snd].push(it.fst);
        }
        forns(i,1,n+1){
            if(place[i].size()){
                prioridad.push({place[i].front(),i});
                place[i].pop();
            }
            else{
                prioridad.push({INT_MAX,i});
            }
        }
        ll cur=0;//POSICIÓN ACTUAL
        int indx=0;//posición gasolinera
        charge.pb({LLONG_MAX,1});
        for(auto it:charge){
        }
        for(int i=0;i<charge.size();i++){
            pair<ll , ll >gasAct=charge[i];
            while(cur<gasAct.first and prioridad.size()){
                ll batAct=prioridad.top().second;
                if(cur+battery[batAct]>gasAct.first){
                    ll dif=gasAct.first-cur;
//                    cout<<dif<<" -"<<"\n";
                    battery[batAct]-=dif;
                    cur=gasAct.first;
                    break;
                }
                else{
                    cur+=battery[batAct];
                    battery[batAct]=0;
                    prioridad.pop();
                }
            }
            battery[gasAct.second]=tope[gasAct.second];
            int indx=gasAct.second;
            if(place[indx].size())place[indx].pop();
            if(place[indx].size()){
                prioridad.push({place[indx].front(),indx});
            }
            else{
                prioridad.push({INT_MAX,indx});
            }
            while(prioridad.size() and prioridad.top().first<=cur)prioridad.pop();
        }
        cout<<cur<<"\n";
    }
}