#include <bits/stdc++.h>
using namespace std;
#define db(x) cerr<<#x<<(x)<<"\n"
#define db1(x) cerr<<#x<<(x)<<" "
#define rep(i,a,b) for(auto i=(a);i<=(b);i++)
#define ll long long
const int N = 1e5+10;
int n,m;
ll x[N],id[N],a[N],na[N],pos[N],net[N],pre[N];
ll ans;
int num[N];
vector<int> kpos[N];
const ll inf = 1e18;
int tot;
struct st{
    ll idx,pos;
    bool operator<(const st& T)const {
        return pos>T.pos;
    }
};
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];na[i] = a[i];
    }
    x[0]=0;
    for(int i=1;i<=m;i++){
        cin>>x[i]>>id[i];
        if(pos[id[i]]==0)pos[id[i]] = x[i];
        int k  = id[i];
        net[pre[k]] = i;
        pre[k] = i;
        kpos[k].push_back(i);
        
    }
    x[m+1] = x[m]+1;
    for(int i=1;i<=m;i++){
    	if(net[i]== 0)net[i] =m+1; //走向最后一个
    }
    priority_queue<st>q;
     map<int,int> mp;
    for(int i=1;i<=n;i++){
        if(pos[i]){
        	//第一个的位置
            q.push({i,pos[i]});
            ++num[i];
        }else {
            ++tot;
            q.push({i,x[m+1]});
        }
        mp[i] =1;
    }
    auto q1 =q;
    auto pr = [&](){
    	for(int i=1;i<=n;i++)cout<<na[i]<< " ";cout<<"\n";
    };
    // while(q1.size()){
    	// //cout<<q1.top().w<<" "<<q1.top().idx<<" \n";q1.pop();
    // }
    for(int i=1;i<=m;i++){
        ll dis = x[i]-x[i-1];
        ll tmp =0,f =0;
        while(q.size()){
            auto [idx,pos] = q.top();q.pop();
         //   cout<<"i --"<<i<<"使用idx = "<<idx<<"\n";
            mp[idx] =0;//该电池已经用完了
            if(tmp+na[idx]<=dis){
            	//tmp代表当前走的距离+优先使用的电池<=dis,那么都将电池用完，丢弃，
            	//只有再次充电时才能用，直接丢弃，以后再加进来
                tmp+=na[idx];
            }else if(tmp+na[idx]>dis){
            	//电池暂时不能丢弃，那么该电池为临时电池,na[]值依旧要改变
            	//若为后续充电电池后，na[i]会增加就好
                ll res = dis-tmp;
                tmp=dis;//走到地方了
                na[idx]-=res;
            	if(num[idx]<kpos[idx].size())q.push({idx,x[kpos[idx][num[idx]]]}),num[idx]++;
            	else q.push({idx,x[m+1]});
            //	num++; 
            	mp[idx] =1;
            }
           // pr();
            if(tmp==dis){
                f =1; //跳出
                break;
            }
        }
        if(f==0){
        	//走不到当前点
            ans = x[i-1]+tmp;
            cout<<ans<<"\n"; return;
        }
          //	pr();
          	int k = id[i];
          	na[k] = max(na[k],a[k]);
         //   na[id[i]] = max(a[id[i]],na[id[i]]);
          //   cout<<"更新后q.size()"<<q.size()<<"\n"; pr();
          //  cout<<"i = "<<" "<<id[i]<<"\n";
            if(!mp[id[i]]){ 
            	ll netpos = x[net[k]];
            	q.push({k,netpos});
            	//cout<<"加入 "<<k<<"\n";
            }
        }
	    ans = x[m];
	    while(q.size()){
	        auto [idx,pos] = q.top();q.pop();
	  //      cout<<"idx<<"<<idx<<"\n";
	        ans+= na[idx];
	     //   db(ans);
	    }
    cout<<ans<<"\n";
    for(int i=1;i<=n;i++)pos[i] =net[i] =0,kpos[i].clear();
    ans =0;
    return ;
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int _ ;cin>>_;while(_--)solve();
}