#include<bits/stdc++.h>
namespace my_std{
    using namespace std;
    #define pii pair<int,int>
    #define fir first
    #define sec second
    #define MP make_pair
    #define rep(i,x,y) for (int i=(x);i<=(y);i++)
    #define drep(i,x,y) for (int i=(x);i>=(y);i--)
    #define go(x) for (int i=head[x];i;i=edge[i].nxt)
    #define templ template<typename T>
    #define sz 303030
    typedef long long ll;
    typedef double db;
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    templ inline T rnd(T l,T r) {return uniform_int_distribution<T>(l,r)(rng);}
    templ inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
    templ inline bool chkmin(T &x,T y){return x>y?x=y,1:0;}
    templ inline void read(T& t) {
        t=0;char f=0,ch=getchar();double d=0.1;
        while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
        while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();
        if(ch=='.'){ch=getchar();while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();}
        t=(f?-t:t);
    }
    template<typename T,typename... Args>inline void read(T& t,Args&... args){read(t); read(args...);}
    void file() {
        #ifdef zqj
        freopen("a.in","r",stdin);
        #endif
    }
    inline void chktime() {
        #ifdef zqj
        cerr<<clock()/1000.0<<'\n';
        #endif
    }
    #ifdef mod
    ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x%mod) if (y&1) ret=ret*x%mod;return ret;}
    ll inv(ll x){return ksm(x,mod-2);}
    #else
    ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x) if (y&1) ret=ret*x;return ret;}
    #endif
}
using namespace my_std;

int n,m;
ll a[sz];

const int Tree=sz*50;
int ch[Tree][2],root,cc;
ll sum[Tree];
#define ls ch[k][0]
#define rs ch[k][1]
#define lson ls,l,mid
#define rson rs,mid+1,r
void pushup(int k,ll l,ll r) {
    sum[k]=0;
    ll mid=(l+r)>>1;
    sum[k]+=(ls?sum[ls]:mid-l+1);
    sum[k]+=(rs?sum[rs]:r-mid);
}
void modify(int &k,ll l,ll r,ll x,ll y) {
    if (!k) k=++cc,sum[k]=r-l+1,ls=rs=0;
    if (x<=l&&r<=y) return sum[k]=0,void();
    ll mid=(l+r)>>1;
    if (x<=mid) modify(lson,x,y);
    if (y>mid) modify(rson,x,y);
    pushup(k,l,r);
}
ll walk(int k,ll l,ll r,ll x,ll &dis) {
    assert(x<=r);
    if (!k) {
        if (dis>=r-max(l,x)+1) {
            dis-=r-max(l,x)+1;
            return r;
        }
        ll res=max(l,x)+dis-1;
        dis=0;
        return res;
    }
    if (!sum[k]) return r;
    if (x<=l&&sum[k]<=dis) {
        dis-=sum[k];
        return r;
    }
    if (l==r) return l-1;
    ll mid=(l+r)>>1;
    if (x<=mid) {
        ll res=walk(lson,x,dis);
        if (res<mid) return res;
    }
    return walk(rson,x,dis);
}


void work() {
    cin>>n>>m;
    rep(i,1,n) cin>>a[i];
    const ll R=1e15;
    root=cc=1,ch[1][0]=ch[1][1]=0,sum[1]=R;
    static int pos[sz];
    rep(i,1,n) pos[i]=0;
    rep(_,1,m) {
        ll x; int ty; cin>>x>>ty;
        ll tmp=a[ty];
        ll to=walk(root,1,R,pos[ty]+1,tmp);
        modify(root,1,R,pos[ty]+1,min(x,to));
        pos[ty]=x;
    }
    static pii b[sz];
    rep(i,1,n) b[i]=MP(pos[i],i);
    sort(b+1,b+n+1);
    ll cur=0,dis=0;
    rep(i,1,n) {
        cur=walk(root,1,R,cur+1,dis);
        if (cur>=b[i].fir) dis+=a[b[i].sec];
        else break;
    }
    cur=walk(root,1,R,cur+1,dis);
    cout<<cur<<'\n';
}

int main() {
    file();
    int T; cin>>T;
    while (T--) work();
    return 0;
}