#include <bits/stdc++.h>
#define endl '\n'

using ll = long long;

constexpr int N = 2e5 + 10;
constexpr int mod = 998244353;

using namespace std;

void solve(){
	int n, m;
	cin >> n >> m;
	vector<int> a(n + 1), avail(n + 1);
	for (int i = 1; i <= n; ++i) cin >> a[i], avail[i] = a[i];
	vector<int> pos(m + 1), id(m + 1);
	map<int, int> idx;

	deque<int> q;
	vector<int> vis(n + 1);
	vector<vector<int>> lst(n + 1);
	vector<int> its(n + 1);
	for (int i = 1; i <= m; ++i) {
		cin >> pos[i] >> id[i];
		idx[pos[i]] = id[i];
		lst[id[i]].push_back(pos[i]);
		q.push_back(id[i]);
	}
	ll free = 0, cur = 0;
	set<int> s;
	for (int i = 1; i <= n; ++i) {
		if (lst[i].size() == 0) {
			free += avail[i];
			avail[i] = 0;
		}else {
			s.insert(i);
		}
	}

	//cout << "free : " << free << endl;

	for (int i = 1; i <= m; ++i) {
		int nxt = pos[i];
		int det = nxt - cur;
		while (det && !q.empty()) {
			auto u = q.front();
			q.pop_front();
			if (s.find(u) == s.end()) continue;
			auto it = s.find(u);
			its[u]++;
			int d = min(det, avail[u]);
			det -= d;
			avail[u] -= d;
			if (its[u] >= lst[u].size()) {
				free += avail[u];
				s.erase(it);
			}else if (avail[u] == 0) {
				s.erase(it);
			}
		}  

		if (det > free) {
			cout << cur + (nxt - cur) - det + free << endl;
			return;
		}else {
			free -= det;
		}

		if (s.find(idx[pos[i]]) != s.end()) {
			s.erase(s.find(idx[pos[i]]));
		}
		
		if (its[idx[pos[i]]] >= lst[idx[pos[i]]].size()) {
			free -= avail[idx[pos[i]]];
			free += a[idx[pos[i]]];
		}else {
			s.insert(idx[pos[i]]);
		}
		avail[idx[pos[i]]] = a[idx[pos[i]]];
		cur = nxt;
	}

	//cout << "free : " << free << endl;

	cout << cur + free << endl;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while(t--) solve();
    return 0;
}

/*
2
3 1
3 3 3
8 1
2 2
5 2
1 2
2 1
*/

/*
1
2 2
5 2
1 2
2 1
*/