#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int INF = 1e18;
const int N = 1e6 + 10;
const int M = 5020;
const int mod = 998244353;
typedef pair<int,int> PII;
typedef pair<int,PII> pii;
int n,m;
int a[N];
int d[N],b[N],pre[N],num[N];
int x,y;

void solve(){
	cin >> n >> m;
	map<int,int> mm;
	x = 0,y = 0;
	for(int i=1; i<=n; i++) cin >> a[i];
	for(int i=1; i<=m; i++){
		cin >> d[i] >> b[i];
		pre[i] = mm[b[i]];
		mm[b[i]] = i; 
	}
	for(int i=1; i<=n; i++){
		if(mm[i] > 0) y += a[i];
		else x += a[i];
	}
	int sum = y;
	int now = 0;
	vector<PII> v;
	for(int i=1; i<=m; i++){
		int len = 0;
		int xx = d[i] - d[i - 1];
		int dy = 0;
		if(len != xx){
			len = min(y,xx);
			y -= len;
			dy = len;
		}
		if(len != xx){
			int kk = min(xx - len, x);
			x -= kk;
			len += kk;
		}
		now += len;
		int kk = 0;
		int yy = a[b[i]];
		if(len != xx) break;
		else{
			if(dy >= a[b[i]]){
				y += a[b[i]];
				v.push_back({i,dy - a[b[i]]});
			}else{
				yy = a[b[i]] - dy;
				while(v.size() && v.back().first > pre[i] && yy > 0){
					if(v.back().second >= dy) v.back().second -= yy,kk+=yy,yy=0;
					else kk+=yy - v.back().second,yy -= v.back().second,v.pop_back();
				}	
				y += kk + dy;
			}
			if(mm[b[i]] == i) x += a[b[i]],y -= a[b[i]],sum -= a[b[i]]; 
		}
		//cout << y << ' ' << x << ' ' << kk << endl;
	}
	now += x + y;
	cout << now << endl;
}

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