#include <bits/stdc++.h>
#define int long long 
#define pb push_back
using namespace std;
const int INF=3e5+5;
int n,m,a[INF],x[INF],t[INF],pre[INF];
struct P2{
    int dis_v,pos,w;
    bool operator < (const P2 &x) const{
        if (x.dis_v!=dis_v) return x.dis_v>dis_v;
        else if (x.pos!=pos) return x.pos>pos;
        else return x.w>w;
    }
};
void solve() {
    cin>>n>>m;map <int,int> Map;
    for (int i=1;i<=n;i++) cin>>a[i];
    for (int i=1;i<=m;i++) cin>>x[i]>>t[i];
    int N=2e9;
    for (int i=n;i;i--) {
        if (!Map[t[i]]) pre[i]=N;
        else pre[i]=Map[t[i]];
        Map[t[i]]=i;
    }
    multiset <P2> s1;
    for (int i=1;i<=n;i++) 
        if (Map[i]) s1.insert({Map[i],i,a[i]});
        else s1.insert({N,i,a[i]});
    x[0]=0;
    for (int i=1;i<=n;i++) {
        // x[i]-x[i-1]    
        int it=x[i]-x[i-1];
        while (s1.size()) {
            auto it5=*s1.begin();
            s1.erase(s1.begin());
            int xx=min(it,it5.w);
            it-=xx;it5.w-=xx;
            if (it5.w) {s1.insert(it5);break;}
        }
        if (!it) {
            auto it=s1.lower_bound({i,t[i],0});
            if (it!=s1.end() && it->pos==t[i]) s1.erase(it);
            s1.insert({pre[i],t[i],a[t[i]]});
        } else {cout<<x[i-1]+(x[i]-x[i-1]-it)<<"\n";return ;}
    }
    int res=0;
    for (auto it:s1)
        res+=it.w;
    cout<<x[n]+res<<"\n";
}
signed main()
{
    ios::sync_with_stdio(false);
    int t=1;cin>>t;
    while (t--) solve();
    return 0;
}