#include<bits/stdc++.h>
#define INF 2147483647LL
#define int long long
#define MAXN 500005
#define mod 1000000007
#define PI 3.14
#define eps 1e-10
#define pa pair<int,int>
#define ms(a,x) memset(a,x,sizeof(a))
#define mc(ar1,ar2) memcpy(ar1,ar2,sizeof(ar2))
#define mkp(a,b) make_pair(a,b)
#define ls (p<<1)
#define rs (p<<1|1)
#define fn(i,st,ed) for(int i=st;i<=ed;++i)
#define fd(i,st,ed) for(int i=st;i>=ed;--i)
#define fg(i,x,head,e) for(int i=head[x];~i;i=e[i].nxt)
using namespace std;
inline int read(){int x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f;}
int a[MAXN],x[MAXN],t[MAXN],lst[MAXN],dis[MAXN],nowdis[MAXN];
void solve(){
    int n,m,ans=0,sum=0;cin>>n>>m;
    fn(i,1,n)cin>>a[i];
    fn(i,1,m)cin>>x[i]>>t[i];
    fn(i,1,n)t[m+i]=i;
    fn(i,1,n)nowdis[i]=0;
    fd(i,n+m,1)lst[i]=nowdis[t[i]],nowdis[t[i]]=i;
    fn(i,1,n)dis[i]=a[i];
    fn(i,1,n)sum+=dis[i];
    priority_queue<int,vector<int>,greater<int> >q;
    fn(i,1,n+m)q.push(i);
    fn(i,1,m){
        int tmp=x[i]-x[i-1];
        while(!q.empty()&&q.top()<i)q.pop();
        while(tmp&&!q.empty()){
            int stp=t[q.top()],len=min(tmp,dis[stp]);
            dis[stp]-=len,sum-=len,tmp-=len;
            if(!dis[stp])q.pop();
        }
        if(tmp)break;
        sum+=a[t[i]]-dis[t[i]];
        dis[t[i]]=a[t[i]];
        ans=max(ans,x[i]+sum);
        if(lst[i])q.push(lst[i]);
    }
    cout<<ans<<endl;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--){solve();}
    return 0;
}