#include <bits/stdc++.h>
using namespace std;
#define ls (rt << 1)
#define rs (rt << 1 | 1)

using i64 = long long;

struct Segment {
    vector<i64> f, tag;

    void init(int l, int r, int rt, int a, int b, i64 c) {
        if (l >= a && r <= b) {
            f[rt] = c;
            return;
        }

        int mid = (l + r) >> 1;
        if (mid >= a) {
            init(l, mid, ls, a, b, c);
        }
        if (mid + 1 <= b) {
            init(mid + 1, r, rs, a, b, c);
        }
        push_up(rt);
    }

    void push_up(int rt) {
        f[rt] = f[ls] + f[rs];
    }

    void push_down(int rt) {
        if (tag[rt] != 0) {
            i64 t = tag[rt];
            tag[rt] = 0;
            int t1 = min(f[ls], t), t2 = t - t1;
            f[ls] -= t1, tag[ls] += t1;
            f[rs] -= t2, tag[rs] += t2;
        }
    }

    void update(int l, int r, int rt, int a, int b, i64 &c) {
        if (l >= a && r <= b) {
            i64 t = min(f[rt], c);
            f[rt] -= t;
            c -= t;
            tag[rt] += t;
            return;
        }

        push_down(rt);
        int mid = (l + r) >> 1;
        if (mid >= a) {
            update(l, mid, ls, a, b, c);
        }
        if (mid + 1 <= b) {
            update(mid + 1, r, rs, a, b, c);
        }
        push_up(rt);
    }

    i64 query(int l, int r, int rt, int a, int b) {
        if (l >= a && r <= b) {
            return f[rt];
        }

        push_down(rt);
        int mid = (l + r) >> 1;
        i64 ret = 0;
        if (mid >= a) {
            ret += query(l, mid, ls, a, b);
        }
        if (mid + 1 <= b) {
            ret += query(mid + 1, r, rs, a, b);
        }
        return ret;
    }

    void In(int n) {
        f.assign(n << 2, 0);
        tag.assign(n << 2, 0);
    }

    void Re(int n) {
        for (int i = 1; i < (n << 2); i++) {
            f[i] = tag[i] = 0;
        }
    }
};

Segment f;

void solve() {
    int n, m;
    cin >> n >> m;

    i64 b = 0;
    vector<i64> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        b += a[i];
    }

    vector<int> x(m + 1, 0), t(m + 1);
    for (int i = 1; i <= m; i++) {
        cin >> x[i] >> t[i];
        t[i]--;
        f.init(1, n, 1, i, i, x[i] - x[i - 1]);
    }

    i64 ans = 0;

    vector<int> last(n, 0);

    for (int i = 1; i <= m; i++) {
        i64 cost = x[i] - x[i - 1];
        if (b < cost) {
            ans = x[i - 1] + b;
            break;
        } else {
            i64 cal = f.query(1, n, 1, last[t[i]] + 1, i), can = min(a[t[i]], i64(x[i] - x[last[t[i]]]));
            if (cal >= can) {
                b = b - cost + can;
                f.update(1, n, 1, last[t[i]] + 1, i, can);
            } else {
                b = b - cost + cal;
                f.update(1, n, 1, last[t[i]] + 1, i, cal);
            }

            last[t[i]] = i;

            if (i == m) {
                ans = x[i] + b;
            }
        }
    }

    cout << ans << endl;

    f.Re(n);
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    f.In(2e5);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}