#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(0), cin.tie(0)
#define time chrono::system_clock::now().time_since_epoch().count()
using namespace std;
#define int long long
using ll = long long;
using pll = pair<int, int>;

const int mod = 1e9 + 7, N = 2e5 + 10;

void solve(){
    int n, m; cin >> n >> m;
    vector<int> a(n + 10), st(n + 10);
    for (int i = 1; i <= n; i ++) cin >> a[i], st[i] = a[i];
    vector<pll> b(m + n + 10);
    vector<int> nx(n + m + 10);
    for (int i = 1; i <= m; i ++) {
        cin >> b[i].first >> b[i].second;
    }
    for (int i = 1; i <= n; i ++) {
        b[m + i] = {1e18, i};
    }
    vector<int> mp(n + 10, n + m + 1);
    for (int i = n + m; i >= 1; i --) {
        nx[i] = mp[b[i].second];
        mp[b[i].second] = i;
    }

    multiset<tuple<int, int, int>> s;
    for (int i = 1, j = 1; i <= n + 1; i ++) {
        int dis = b[i].first - b[i - 1].first;
        while (j < i) j ++;
        while (s.size() && dis) {
            auto [p, id, v] = *s.begin();
            s.erase(s.find({p, id, v}));
            if (p < i) {
                if (nx[p] < j && nx[p] >= i && a[b[nx[p]].second]) s.insert({nx[p], b[nx[p]].second, a[b[nx[p]].second]});
                else continue;
            }
            int t = min(dis, v);
            dis -= t;
            a[id] -= t;
            if (v - t > 0) s.insert({p, id, v - t});
        }
        while(dis && j <= n + m) {
            int t = min(a[b[j].second], dis);
            dis -= t;
            a[b[j].second] -= t;
            j ++;
        }
        j--;
        if (dis) {
            int t = b[i].first - dis;
            cout << t << '\n';
            return;
        }
        a[b[i].second] = st[b[i].second];
        if (nx[i] >= j) continue;
        else {
            s.insert({nx[i], b[i].second, a[b[i].second]});
        }
    }
}

signed main()
{
    ios;
    int t = 1;
    cin >> t;
    while (t--)
        solve();
    return 0;
}