#include <bits/stdc++.h>
typedef long long ll;typedef unsigned long long ull; typedef double db;typedef long double ldb;
#define fre(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)
#define Rep(i,a,b) for(int i=a;i<=b;++i) 
#define Dwn(i,a,b) for(int i=a;i>=b;--i)
#define pii pair<int,int>
#define mair make_pair
#define fir first
#define sec second
using namespace std;

const int maxn=1e5+10;

int n,m;
ll sum;
int a[maxn],b[maxn];
int x[maxn],t[maxn];
vector<int>vec[maxn];

struct Ver{
	int x,t;
	bool operator < (const Ver &rhs)const{
		if(x!=rhs.x)return x<rhs.x;
		else return a[t]>=a[rhs.t];
	}
};

set<Ver>S;

void Add(int p,ll pos){
	while(!vec[p].empty() && vec[p].back()<=pos)vec[p].pop_back();
	if(!vec[p].empty())S.insert(Ver{vec[p].back(),p});
}

set<int>rec,Pos;
vector<int>Ec[maxn];
unordered_map<int,int>Map;

int Id(int x){ if(!Map.count(x))return Map[x]=Map.size()+1; else return Map[x]; }

void solve(){
	cin>>n>>m;S.clear();rec.clear();Pos.clear();Map.clear();
	Rep(i,1,n)cin>>a[i],vec[i].resize(0),b[i]=a[i],rec.insert(i),Ec[i].resize(0);
	Rep(i,1,m)cin>>x[i]>>t[i],vec[t[i]].emplace_back(x[i]),Pos.insert(x[i]),Ec[Id(x[i])].emplace_back(t[i]);
	Rep(i,1,n){
		reverse(vec[i].begin(),vec[i].end());
		if(!vec[i].empty())S.insert(Ver{vec[i].back(),i});
	}
	ll ans=0;
	while(!S.empty() || !rec.empty()){
		auto ip =Pos.upper_bound(ans);
		if(ip==Pos.end())break;
		int nxt=*ip;
		if(!S.empty()){
			Ver it= *S.begin();
			if(!b[it.t] || it.x<=ans)continue;
			if(b[it.t]<nxt-ans){
				ans+=b[it.t];b[it.t]=0;
				rec.erase(it.t);
				S.erase(S.begin());
			}else{
				b[it.t]-=(nxt-ans);
				ans=nxt;
				for(auto it :Ec[Map[nxt]])b[it]=a[it],Add(it,ans),rec.insert(it);
			}
		}else{
			int it=*rec.begin();
			if(b[it]<nxt-ans){
				ans+=b[it];b[it]=0;
				rec.erase(it);
			}else{
				b[it]-=(nxt-ans);
				ans=nxt;
				for(auto it : Ec[Map[nxt]])b[it]=a[it],Add(it,ans),rec.insert(it);
			}
		}
	}
	Rep(i,1,n)ans+=b[i];
	cout<<ans<<"\n";
}

int tex;
int main (){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>tex;while(tex--)solve(); }