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

typedef pair<int,int> pii;
vector<pii>G[101];
int link[101];
void solve() {
    int l,r;
    cin >> l >> r;
    memset(link,-1,sizeof link);
    int node = 2,tar = 2;//起点为1 终点为2
    int mx = -1;
    function<void(int,int,int)> dfs = [&](int l,int r,int k) -> void{
        /*
            100011 0 10100 -> 10100 ~ 11111
            100011 1 11110 -> 00000 ~ 11110
            1 0 100 -> 100 ~ 111
            1 1 111 -> 000 ~ 111
            ~~~~~~~~~~~~~~~~~~~~
            0 0001 -> 0001 ~ 1111 
            1 1110 -> 0000 ~ 1110

            0 001 -> 001 ~ 111 
            1 111 -> 000 ~ 111 X

            0 01 -> 01 ~ 11
            1 11 -> 00 ~ 11 X

            0 1 -> 1 ~ 1 X
            1 1 -> 0 ~ 1 X

            0 000 -> 000 ~ 111 X
            1 110 -> 000 ~ 110 

            0 00 -> 00 ~ 11 X
            1 10 -> 00 ~ 10

            0 0  -> 0 1 X
            1 0  -> 0 0 X
        */
        int now = k;
        int x = -1;
        int t = 19;
        if(l == r and (l == 0 || l == 1)) {
            G[now].push_back({tar,l});
            return;
        }
        while(!(r >> t & 1))t --;
        if(l == r) {
            for(int i = t;i;i -- ) {
                G[now].push_back({++ node,(r >> i & 1)});
                now = node;
            }
            G[now].push_back({tar,r & 1});
            return;
        }
        for(int i = t;i >= 0;i -- ) {
            if((r >> i & 1) != (l >> i & 1))  {
                x = i;
                break;
            }else {
                G[now].push_back({++ node,(r >> i & 1)});
                now = node;
            }
        }
        if(l == 0 and r == (1 << x + 1) - 1) {
            // link 到 i -> i + 1 {0,1}的链
            link[now] = x;
            mx = max(mx,x);
            return;
        }
        int s = l >> x << x;
        if(x == 0) {
            G[now].push_back({tar,1});
            G[now].push_back({tar,0});
            return;
        }
        // cout << l - s << ' ' << (1 << x) - 1 << endl;
        // cout << 0 << ' ' << r - s - (1 << x) << endl;
        G[now].push_back({node + 1,0});
        G[now].push_back({node + 2,1});
        int d = node;
        node += 2;

        dfs(l - s,(1 << x) - 1,d + 1);

        int j = (__lg(r - s - (1 << x)));
        now = d + 2;
        while(x != j + 1) {
            G[now].push_back({++ node,0});
            now = node;
            j ++;
        }
        //if(d == 7)cout << d + 2 << now << "\n";
        dfs(0,r - s - (1 << x),now);
    };
    int f1 = -1,f2 = -1;
    for(int i = 0;i < 20;i ++ ) {
        if(l >> i & 1)f1 = i;
        if(r >> i & 1)f2 = i;
    }
    int L = l;
    for(int i = f1 + 1;;i ++ ) {
        int R = (1 << i) - 1;
        R = min(R,r);
        dfs(L,R,1);
        if(R >= r) {
            break;
        }
        L = R + 1;
    }

    if(mx != -1) {
        G[node + 1].push_back({tar,1});
        G[node + 1].push_back({tar,0});
        for(int i = 2;i <= mx;i ++ ) {
            G[node + i].push_back({node + i - 1,1});
            G[node + i].push_back({node + i - 1,0});
        }

        for(int i = 1;i <= node;i ++ ) {
            int x = link[i];
            if(x == -1)continue;
            // cout << i << ' ' << x << '\n';
            if(x == 0) {
                G[i].push_back({tar,1});
                G[i].push_back({tar,0});
            }
            else {
                G[i].push_back({node + x,1});
                G[i].push_back({node + x,0});
            }
        }
    }
    /*cout << node + mx << "\n";
    for(int i = 1;i <= node + mx;i ++ ) {
        cout << G[i].size() << " ";
        for(auto [v,w] : G[i]) {
            cout << v << ' ' << w << ' ';
        }
        cout << "\n";
    }*/
    for(int i = 1;i <= node + mx;i ++ ) {
        for(auto [v,w] : G[i]) {
            cout << i << ' ' << v << ' ' << w << '\n';
        }
    }
    
}
void solveK() {
    ll n,m;
    cin >> n >> m;
    vector<ll>w(n),l(n),r(n),p(n);
    ll s = 0;
    for(int i = 0;i < n;i ++ ) {
        cin >> w[i] >> l[i] >> r[i];
        s += l[i];
    }
    iota(p.begin(),p.end(),0);
    sort(p.begin(),p.end(),[&](int a,int b) {
        return w[a] > w[b];
    });
    
    vector<ll>rs(n + 1),ls(n + 1),d(n + 1);
    for(int i = 0;i < n;i ++ ) {
        int id = p[i];
        ls[i + 1] = ls[i] + w[id] * l[id];
        rs[i + 1] = rs[i] + w[id] * r[id];
        d[i + 1] = d[i] + (r[id] - l[id]);
    }
    ll t = m - s,ans = 0;
    for(int i = 1;i <= n;i ++ ) {
        int id = p[i - 1];
        t += l[id];
        int pos = upper_bound(d.begin() + 1,d.end(),t) - d.begin() - 1;
        ll res = 0;
        if(pos < i) {
            ll det = t - d[pos];// pos + 1 <= i - 1
            res = rs[pos] + w[p[pos]] * det + (ls[n] - ls[i]) + (pos + 1 <= i - 1 ? (ls[i - 1] - ls[pos]) : 0);
        }else {
            ll det = t - d[i - 1];
            res = rs[i - 1] + w[id] * det + (ls[n] - ls[i]);
        }
        ans = max(ans,res); 
        t -= l[id];
    }
    cout << ans << "\n";
}
const int N = 1e5 + 5;
struct Node
{
    int l,r;
    int x,len;
}tr[N << 2];
int a[N],b[N];
vector<int>p,d;
void pushup(int u) {
    if(tr[u << 1].x == tr[u << 1].len)
    tr[u].x = tr[u << 1].x + tr[u << 1 | 1].x;
    else tr[u].x = tr[u << 1].x;
}
void build(int u,int l,int r) {
    tr[u] = {l,r,0,r - l + 1};
    if(l == r) {
        if(a[p[l]] == 0)tr[u].x = 1;
        else tr[u].x = 0;
        return;
    }
    int mid = l + r >> 1;
    build(u << 1,l,mid);
    build(u << 1 | 1,mid + 1,r);
    pushup(u);
}
void modify(int u,int x,int c) {
    if(tr[u].l == tr[u].r) {
        if(c == 0)tr[u].x = 1;
        else tr[u].x = 0;
        return;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    if(x <= mid)modify(u << 1,x,c);
    else modify(u << 1 | 1,x,c);
    pushup(u);
}
int query(int u,int l,int r) {
    if(tr[u].l >= l and tr[u].r <= r) {
        if(tr[u].x == tr[u].len)return -1;
        else return tr[u].x + tr[u].l;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    if(l <= mid) {
        int x = query(u << 1,l,r);
        if(x != -1)return x;
    }
    if(r > mid) return query(u << 1 | 1,l,r);
    assert(0);
    return -1;
    /*int x = query(u << 1,l,r);
    if(x == -1) {
        return query(u << 1 | 1,l,r);
    }else return x;*/
}
void solveJ(int TestCase) {
    int n,m;
    cin >> n >> m;
    for(int i = 1;i <= n;i ++ ) {
        cin >> a[i];
        b[i] = a[i];
    }
    int pre = 0;
    d.clear(),p.clear();
    p.push_back(0);
    d.push_back(0);
    vector<int>st(n + 1);
    for(int i = 1;i <= m;i ++ ) {
        int x,t;
        cin >> x >> t;
        int dis = x - pre;
        pre = x;
        p.push_back(t);
        st[t] ++;
        d.push_back(dis);
    }
    build(1,1,m);
    ll sum = 0;
    for(int i = 1;i <= n;i ++ ) {
        if(!st[i])sum += a[i];
    }
    int k = 0;
    ll ans = 0;
    bool f = 0;
    for(int i = 1;i <= m;i ++ ) {
        int dis = d[i];
        // if(i == 2)cerr << ans + sum << "\n";
        while(dis > 0) {
            int pos = query(1,1,m);
            // cerr << pos << "\n";
            // if(TestCase == 0)cerr << pos << "\n";
            if(pos == -1) {
                // cerr << sum << ' ' << dis << "\n";
                if(sum >= dis) {
                    ans += dis;
                    sum -= dis;
                    dis = 0;
                }else {
                    ans += sum;
                    dis -= sum;
                    sum = 0;
                    f = 1;break;
                }
            }else {
                // cerr << a[p[pos]] << ' ' << dis << "\n";
                if(dis >= a[p[pos]]) {
                    ans += a[p[pos]];
                    dis -= a[p[pos]];
                    modify(1,pos,0);
                    a[p[pos]] = 0;
                }else {
                    ans += dis;
                    a[p[pos]] -= dis;
                    dis = 0;
                }
            }
        }
        if(f == 1)break;
        modify(1,i,1);
        a[p[i]] = b[p[i]];
        --st[p[i]];
        if(st[p[i]] == 0) sum += a[p[i]],modify(1,i,0);
        // cerr << sum << "\n";
    }
    ans += sum;
    cout << ans << "\n";
}
int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    cin >> T;
    while(T -- ) {
        solveJ(T);
    }
    return 0;
}