#include <bits/stdc++.h>
#define int long long
using namespace std;
const int inf = 1e9, mod = 1e9 + 7;
typedef long long ll;
int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
        f = (c == '-') ? -1 : 1, c = getchar();
    while (c >= '0' && c <= '9')
        x = x * 10 + c - '0', c = getchar();
    return x * f;
}
struct node {
    int r, v;
    bool operator<(const node &a) const { return r > a.r; }
};
priority_queue<node> q;
int a[100010];
vector<int> b[100010];
queue<int> p[100010];
int c[100010];
int d[100010];
void solve() {
    int n = read(), m = read();
    for (int i = 1; i <= n; i++)
        a[i] = read(), b[i].clear();
    for (int i = 1; i <= m; i++) {
        int x = read(), t = read();
        c[i] = x, d[i] = t;
        b[t].push_back(x);
    }

    for (int i = 1; i <= n; i++) {
        sort(b[i].begin(), b[i].end());
        while (!p[i].empty())
            p[i].pop();
        for (int j = 0; j < b[i].size(); j++)
            p[i].push(b[i][j]);
        p[i].push(5e17);
        q.push({p[i].front(), a[i]});
        p[i].pop();
    }
    c[0] = 0;
    c[m + 1] = 5e17 - 1;
    for (int i = 1; i <= m + 1; i++) {
        int len = c[i] - c[i - 1];
        while (!q.empty()) {
            if (q.top().v >= len) {
                node z = {q.top().r, q.top().v - len};
                len = 0;
                q.pop();
                if (z.v != 0)
                    q.push(z);
                break;
            } else {
                len -= q.top().v;
                q.pop();
            }
        }
        if (len) {
            cout << c[i] - len << "\n";
            return;
        }
        if (q.top().r == c[i])
            q.pop();
        q.push({p[d[i]].front(), a[d[i]]});
        p[d[i]].pop();
    }
}
signed main() {
    int T = read();
    while (T--)
        solve();
}