#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int n, m;
long long a[N], x[N], t[N], sa;

inline bool Chk(long long mid) {
	long long sum = 0;
	int s = m;
	while (s >= 1 && x[s] > mid) s--;
	long long curp = mid;
	//cout << "mid = " << mid << endl;
	for (int i = s;i >= 0;i--) {
		if (sum + curp - x[i] > sa) return 0;
		//cout << i << " " << sum << endl;
		sum += curp - x[i];
		curp = x[i];
		if (i != 0) sum -= min(sum, a[t[i]]);
	}
	return 1;
}

int main() {
	std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tt;
	cin >> tt;
	while (tt--) {
		cin >> n >> m;
		for (int i = 1;i <= n;i++) cin >> a[i];
		for (int i = 1;i <= m;i++) cin >> x[i] >> t[i];
		x[0] = 0;
		sa = 0;
		for (int i = 1;i <= n;i++) sa += a[i];
		long long l = 0, r = 1e18;
		while (l < r - 1) {
			long long mid = l + r >> 1;
			if (Chk(mid)) l = mid;
			else r = mid;
		}
		cout << l << endl;
	}
	return 0;
}