#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define pb push_back
#define pii pair<int,int>
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
using namespace std;
const int N = 100005;
vector<int> a(N);
vector<int> r(N);
vector<int> x(N);
vector<int> t(N);
void solve() {
	int n, m;
	cin >> n >> m;
	queue<int> yxj[n + 1];  //每个电瓶用一个队列存储优先级，即充电站位置
	priority_queue<pii, vector<pii>, greater<pii>> s;// 按照pair的第一个键值升序排列的最小堆
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		r[i] = a[i];
	}
	for (int i = 1; i <= m; i++) {
		cin >> x[i] >> t[i];
		yxj[t[i]].push(x[i]);
	}
	for (int i = 1; i <= n; i++) {
		yxj[i].push(MOD); //给所有电瓶都设置一个极大位置的充电站
	}
	for (int i = 1; i <= n; i++) {
		int f = yxj[i].front();
		yxj[i].pop();
		s.push({f, i});
	}
	int ans = 0 ;
	for (int i = 1; i <= m; i++) {
		int len = x[i] - x[i - 1]; //当前充电站与上一站的距离
		while (len > 0) { //按照优先队列的顺序用电
			if (s.empty())break;
			auto top = s.top();
			s.pop();
			if (a[top.second] == 0)continue;
			if (a[top.second] <= len) {
				len -= a[top.second];
				a[top.second] = 0;
			} else {
				a[top.second] -= len;
				len = 0;
				break;
			}
		}
		if (len > 0) {//如果电量不足以到达充电站
			ans += (x[i] - x[i - 1] - len);
			break;
		} else { //给电瓶充电
			a[t[i]] = r[t[i]];
			int fi = MOD, se = t[i];
			if (!yxj[t[i]].empty()) {
				fi = yxj[t[i]].front();
				yxj[t[i]].pop();
			}
			s.push({fi, se});
			ans += x[i] - x[i - 1];
		}
	}
	for (int i = 1; i <= n; i++) {
		ans += a[i]; //如果有剩余电量，增加到ans中
	}
	cout << ans << endl;

}

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