#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define x first
#define y second

using namespace std;
typedef long long LL;
const int N = 1e5 + 10;

struct battery {
    LL rem;
    int idx;
    bool operator < (const battery& W) const {
        return idx > W.idx;
    } 
};
LL a[N];
pair<LL, LL> pa[N];
int ne_st[N];
int vis[N];

void solve() {
    memset(vis, 0, sizeof vis);
    memset(ne_st, 0, sizeof ne_st);
    priority_queue<battery> pq;
    int n, m;
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }

    for (int i = 1; i <= m; i++) {
        scanf("%lld%lld", &pa[i].x, &pa[i].y);
    }

    for (int i = m; i; i--) {
        int j = pa[i].y;
        if (!vis[j]) vis[j] = i;
        else {
            ne_st[i] = vis[j];
            vis[j] = i;
        }
    }
    
    LL extra = 0;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            extra += a[i];
            continue;
        }
        pq.push({ a[i], vis[i] });
    }

    for (int i = 1; i <= m; i++) {
        LL dis = pa[i].x - pa[i - 1].x;
        LL oil = 0;
        while (pq.size()) {
            oil += pq.top().rem;
            if (oil > dis) {
                auto tmp = pq.top();
                pq.pop();
                if (tmp.idx != i) {
                    tmp.rem = oil - dis;
                    pq.push(tmp);
                }
                break;
            }
            pq.pop();
            if (oil == dis) break;
        }

        if (dis > oil) {
            if (oil + extra < dis) {
                printf("%lld\n", pa[i - 1].x + oil + extra);
                return;
            }
            extra += oil - dis;
        }
        if (!ne_st[pa[i].y]) {
            extra += a[pa[i].y];
        } else {
            pq.push({ a[pa[i].y], ne_st[i] });
        }
    }
    printf("%lld\n", pa[m].x + extra);
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        solve();
    }
    return 0;
}