#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10,M=1e5+10;
class SegT
{
public:
    struct seg
    {
        int l,r;
        ll sum,tag;
        #define l(x) tree[x].l
        #define r(x) tree[x].r
        #define sum(x) tree[x].sum
        #define tag(x) tree[x].tag
    } tree[N*5];
    void pushUp(seg& x,seg l, seg r)
    {
        x.sum = l.sum+r.sum;
    }
    void update(int x,ll v)
    {
        sum(x) = ((ll)(r(x)-l(x)+1)) * v;
        tag(x) = v;
    }
    void pushDown(int x)
    {
        if(tag(x) != -1)
        {
            update(x*2, tag(x));
            update(x*2+1,tag(x));
        };
        tag(x)=-1;
    }
    void build(int x,int l,int r,int* a)
    {
        // printf("%d %d %d\n",x,l,r);
        tag(x)=-1;
        l(x)=l;r(x)=r;
        if(l==r)
        {
            sum(x)=a[l]; 
            return;
        };
        int mid=(l+r)>>1;
        build(x*2,l,mid,a);
        build(x*2+1,mid+1,r,a);
        pushUp(tree[x],tree[x*2],tree[x*2+1]);
    }
    void modify(int x,int l,int r,ll v)
    {
        if(l>r) 
            return;
        if(l(x)>=l && r(x)<=r)
        {
            update(x,v);
            return ;
        };
        pushDown(x);
        int mid=(l(x)+r(x))>>1;
        if(l<=mid)
            modify(x*2,l,r,v);
        if(r>mid)
            modify(x*2+1,l,r,v);
        pushUp(tree[x],tree[x*2],tree[x*2+1]);
    }
    
    seg query(int x,int l,int r)
    {
        // printf("%d %d %d\n",x,l,r);
        if(l(x)>=l && r(x)<=r)
        {
            return tree[x];
        };
        pushDown(x);
        int mid=(l(x)+r(x))>>1;
        seg ans;
        if(l<=mid && r>mid)
            pushUp(ans, query(x*2,l,r), query(x*2+1,l,r));
        else if(l<=mid)
            ans = query(x*2,l,r);
        else if(r>mid)
            ans = query(x*2+1,l,r);
        return ans;
    }
    seg bs(int x,ll v)
    {
        pushDown(x);
        if(l(x)==r(x))
            return tree[x];
        if(tree[x*2].sum >= v)
            return bs(x*2,v);
        else 
        {
            seg tmp = bs(x*2+1, v-tree[x*2].sum);
            tmp.sum+=tree[x*2].sum;
            return tmp;
        }
    }
};
SegT tr;

// int a[]={0,1,1,4,5,1,4,1,9,1,9};
int cap[N],x[M],t[M];
int tcur[N];
int suc[M];
int a[M];
int main()
{
    // tr.build(1,1,10,a);
    // auto res = tr.bs(1,7);
    // printf("%d %d\n",res.l,res.sum);
    // tr.modify(1,1,3,0);
    // res = tr.bs(1,7);
    // printf("%d %d\n",res.l,res.sum);
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        scanf("%d %d",&n,&m);
        for(int i=1;i<=n;i++)
            tcur[i]=m+1;
        for(int i=1;i<=n;i++)
            scanf("%d",&cap[i]);
        for(int i=1;i<=m;i++)
            scanf("%d %d",&x[i],&t[i]);
        
        for(int i=m;i>=1;i--)
        {
            suc[i]=tcur[t[i]];
            tcur[t[i]]=i;
        };

        for(int i=1;i<=m+1;i++)
            a[i]=0;
        for(int i=1;i<=n;i++)
            a[tcur[i]] += cap[i];
        
        // printf("a[i]:\n");
        // for(int i=1;i<=m+1;i++)
        //     printf("%d ",a[i]);
        // printf("\nsuc:\n");
        // for(int i=1;i<=m;i++)
        //     printf("%d ",suc[i]);
        // printf("\n");
        tr.build(1,1,m+1,a);
        
        ll cur=0;
        bool flag=true;
        for(int i=1;i<=m;i++)
        {
            ll val = x[i]-cur;
            auto res = tr.bs(1,val);
            if(res.sum < val)
            {
                printf("%lld\n",cur+res.sum);
                flag=false;
                break;
            };
            tr.modify(1,1,res.l-1,0);
            tr.modify(1,res.l,res.l,res.sum-val);

            tr.modify(1,i,i,0);

            res=tr.query(1,suc[i],suc[i]);
            tr.modify(1,suc[i],suc[i],res.sum + cap[t[i]]);
            cur = x[i];
        };
        if(flag)
            printf("%lld\n",tr.query(1,m+1,m+1).sum + x[m]);
    }
    return 0;
}