#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];
ll ans;
int vis[N];
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];
        int k  = id[i];
        kpos[k].push_back(i);
    }
    x[m+1] = x[m]+1;
    priority_queue<st>q;
    for(int i=1;i<=n;i++){
    	if(kpos[i].size()){
    		q.push({i,x[kpos[i][0]]});++num[i];
    	}else q.push({i,x[m+1]});
    }
    int R =0;
    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();
            if(tmp+na[idx]<=dis){
            	//tmp代表当前走的距离+优先使用的电池<=dis,那么都将电池用完，丢弃，
            	//只有再次充电时才能用，直接丢弃，以后再加进来
                tmp+=na[idx];
                na[idx] =0;
                if(num[idx]<kpos[idx].size())q.push({idx,x[kpos[idx][num[idx]]]}),num[idx]++;
            	else q.push({idx,x[m+1]});
            }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]});
            }
            if(tmp==dis){
                f =1; //跳出
                break;
            }
        }
        if(f==0){
            R =i-1;
            ans = x[R]+tmp;
            break;
        }
       		 R = i;
          	int k = id[i];
          	na[k] = max(na[k],a[k]);
        }
        if(R!=m){
        	cout<<ans<<"\n";
        }else {
        	ans = x[R];
        	while(q.size()){
	        auto [idx,pos] = q.top();q.pop();
	        ans+= na[idx];
	        }
	        cout<<ans<<"\n";
        }
	    for(int i=1;i<=n;i++)num[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();
}