#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mxn=1e5+7,mxm=5e5+7;;
int n,m,a[mxn],x[mxn],t[mxn],c[mxn];
int T,in[mxn],vis[mxn];
struct ST{
    int dis,id;
    bool operator<(const ST& other)const{
        if(c[id]==0) return true;
        if(c[other.id]==0) return false;
        return dis>other.dis;
    }
};
signed main(){   
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin>>T;
    while(T--){
        priority_queue<ST> q;
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>a[i],c[i]=a[i],vis[i]=0;
        for(int i=1;i<=m;i++){
            cin>>x[i]>>t[i];
            q.push({x[i],t[i]});
            vis[t[i]]+=1;
            in[t[i]]=1;
        }
        cout<<q.top().dis<<'\n';
        int tmp=0;
        for(int i=1;i<=n;i++) if(!vis[i]) tmp+=a[i];
        // cout<<tmp<<' ';
        int now=0,ans=0,fg=1;
        while(!q.empty()){
            int to=q.top().dis;
            int y=q.top().id;
            while(now<to){
                while(q.top().dis<=now) q.pop();
                int x=q.top().id;
                int px=q.top().dis;
                if(c[x]==0){
                    int dx=min(tmp,to-now);
                    now+=dx;
                    tmp-=dx;
                    break;
                }
                int dx=min(to-now,c[x]);
                c[x]-=dx;
                if(c[x]==0) 
                    q.pop(),
                    q.push({px,x});
                // if(c[x]==0) in[x]=0;
                now+=dx;
            }
            if(now<to)break;
            c[y]=a[y];
            while(!q.empty() && q.top().dis<=now)q.pop();
            vis[y]--;
            if(vis[y]==0) tmp+=c[y];
            while(!q.empty() && q.top().dis<=now)q.pop();
        }
        // cout<<now<<' '<<tmp<<' ';
        now+=tmp;
        cout<<now<<'\n';
    }
    return 0;
}