#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using db = long double;
mt19937 rnd(time(0));
class JudTime {
public:
    chrono::time_point<chrono::high_resolution_clock> start, end;
    JudTime() : start(chrono::high_resolution_clock::now()) {}
    ~JudTime() {
        end = chrono::high_resolution_clock::now();
        cerr << fixed << setprecision(6) << chrono::duration<double>(end - start).count()
             << " seconds" << endl;
    }
};
const int N = 1e6 + 5;
int a[N];
int b[N];
void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i <= n; i++) a[i] = b[i] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        a[i] = b[i];
    }
    vector<pll> v;
    v.push_back({0, 0});
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        v.push_back({x, y});
    }
    v.push_back({1e9, 0});
    for (int i = 1; i <= m + 1; i++) {
        int cost = v[i].first - v[i - 1].first;
        cost -= a[v[i].second];
        a[v[i].second] = b[i];
        for (int j = i + 1; j <= m; j++) {
            if (cost <= 0) break;
            int org = a[v[j].second];
            a[v[j].second] = max(0, a[v[j].second] - cost);
            cost -= org;
        }
        if (cost > 0) {
            for (int i = 1; i <= n; i++) {
                if (cost <= 0) break;
                int org = a[i];
                a[i] = max(0, a[i] - cost);
                cost -= org;
            }
        }
        if (cost > 0) {
            cout << v[i - 1].first + (v[i].first - v[i - 1].first - cost) << endl;
            return;
        }
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    //   JudTime judTime;
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}