#include<bits/stdc++.h>
#define int long long
using namespace std;
using PII = pair<int,int>;

const int N=1e6+10;
int n,m,_;
int a[N];
PII b[N],d[N];
vector<int> g[N];
int c[N];
void solve(){
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= m; i++) {
		cin >> b[i].first >> b[i].second;
	}
	sort(b + 1,b + 1 + m);
	for (int i =1 ; i <= m; i++) {
		d[i].first = b[i].first;
		if (g[b[i].second].empty()) {
			d[i].second = a[b[i].second];
		}
		g[b[i].second].push_back(i);
	}
	for (int i = 1; i <= n; i++) {
		if (g[i].empty()) {
			d[m + 1].second += a[i];
		}
		g[i].push_back(m + 1);
	}
	int l = 1;
	int pre = 0;
	multiset<PII> st;
	for (int i = 1; i <= m; i++) {
		while (l <= m + 1) {
			while (!st.empty()) {
				auto [u,w] = *st.begin();
				st.erase(st.begin());
				if (w >= d[i].first - pre) {
					if (u != i)st.insert({u,w - (d[i].first - pre)});
					pre = d[i].first;
					break;
				}
				else pre += w;
			}
			if (pre >= d[i].first) break;
			if (d[l].second < d[i].first - pre) {
				// cout << d[l].second << endl;
				pre += d[l].second;
				d[l].second = 0;
				
			}
			else {
				d[l].second -= d[i].first - pre;
				break;
			}
			l++;
		}
		
		if (l > m + 1) break;
		pre = d[i].first;
		int now = b[i].second;
		c[now]++;
		if (g[now][c[now]] >= l)d[g[now][c[now]]].second += a[now];
		else st.insert({g[now][c[now]],a[now]}); 
	}
	pre += d[m + 1].second;
	cout << pre << endl;
}
void clear(){
	for (int i = 0; i <= max(n,m) + 2; i++) {
		a[i] = 0;
		g[i].clear();
		c[i] = 0;
		b[i].first = b[i].second = d[i].first = d[i].second = 0;
	}
	
}
signed main(){
	ios_base::sync_with_stdio(false),cin.tie(0);
	_=1;
	cin >> _;
	while(_--){
		solve();
		clear();
	}
	return 0;
}