#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define int long long
#define x first
#define y second
const int N = 1e5+50;
int n,m;
int a[N];
struct tree
{
    int l,r;
    int sum;
    int lz;
}tr[N*4];

void pushup(int x)
{
    tr[x].sum = tr[2*x].sum + tr[2*x+1].sum;
}

void pushdown(int x)
{
    auto &root = tr[x], &left = tr[2*x],&right = tr[2*x+1];
    if(root.lz)
    {
        left.lz = left.lz + min(root.lz,left.sum);
        left.sum -= min(root.lz,left.sum);
        right.lz = right.lz + root.lz - min(root.lz,left.sum);
        right.sum -= root.lz - min(root.lz,left.sum);
        root.lz = 0;
    }
}

void build(int x,int l,int r)
{
    tr[x] = {l,r};
    if(l == r)
    {
        tr[x] = {l,r,a[r],0};
        return;
    }
    int mid = l + r >> 1;
    build(2*x,l,mid);
    build(2*x+1,mid+1,r);
    pushup(x);
}

void modify(int x,int l,int r,int v)
{
    if(tr[x].l >= l && tr[x].r <= r)
    {
        tr[x].sum -= v;
        tr[x].lz += v;
        return;
    }
    pushdown(x);
    int mid = tr[x].l+tr[x].r >> 1;
    if(l <= mid) modify(2*x,l,r,min(tr[2*x].sum,v));
    if(r > mid) modify(2*x+1,l,r,v - min(tr[2*x].sum,v));
    pushup(x);
}

int query(int x,int l,int r)
{
    if(tr[x].l >= l && tr[x].r <= r)
    {
        return tr[x].sum;
    }
    pushdown(x);
    int mid = tr[x].l+tr[x].r >> 1;
    int res = 0;
    if(l <= mid) res = query(2*x,l,r);
    if(r > mid) res += query(2*x+1,l,r);
    return res; 
}

void miss() {
    cin >> n >> m;
    vector<int>ai(n + 1);
    int tot = 0;
    for(int i = 1; i <= n; i++) {
        cin >> ai[i];
        tot += ai[i];
    }
    vector<int>bi(n + 1,1);
    pii q[m + 1];
    for(int i = 1; i <= m; i++) {
        cin >> q[i].x >> q[i].y;
        a[i] = q[i].x - q[i - 1].x;
    }
    build(1,1,m);
    for(int i = 1; i <= m; i++) {
        int len = q[i].x - q[i - 1].x;
        int x = query(1,1,i);
        if(x > tot) {
            if(i == 1) cout << tot << endl;
            else cout << q[i - 1].x + (tot - query(1,1,i - 1)) << endl;
            modify(1,1,m,query(1,1,m));
            return;
        }
        x = query(1,bi[q[i].y],i);
        modify(1,bi[q[i].y],i,min(ai[q[i].y],x));
        ai[q[i].y] = i;
    }
    cout << q[m].x + tot - query(1,1,m) << endl;
    modify(1,1,m,query(1,1,m));
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	cin >> T;
	while(T--) miss();
	//system("pause");
}