#include <bits/stdc++.h>
#define int long long
using namespace std;
const double eps = 1e-8;

void solve() {
    int n, m, res = 0;
    cin >> n >> m;
    vector<int> a(n + 1), ta(n + 1), lst(n + 1);
    vector<pair<int, int>> b(m + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        ta[i] = a[i];
    }
    for (int i = 1; i <= m; ++i)  cin >> b[i].first >> b[i].second;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q1, q2;
    priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> q3;
    for (int i = 1; i <= m; ++i)  q1.push(b[i]);
    for (int i = 0; q1.size() != 0 ; res = i) {
        auto t1 = q1.top();
        q1.pop();
        q2.push(t1);
        if(ta[t1.second] == 0) {
            int d = min(a[t1.second], t1.first - lst[t1.second]);
            q3.push({lst[t1.second], t1.second, d});
        }
        else {
            int ti = i + ta[t1.second];
            ta[t1.second] = 0;
            while(q2.size()) {
                auto t2 = q2.top();
                if(ti < t2.first)  break;
                if(q3.size()) {
                    auto t3 = q3.top();
                    if(t2.first == t3[0]) {
                        q3.pop();
                        ti += t3[2];
                        ta[t3[1]] = a[t3[1]] - t3[2];
                    }
                    else {
                        ta[t2.second] = a[t2.second];
                        if(t1 == t2)  ti = t1.first;
                    }
                }
                else {
                    ta[t2.second] = a[t2.second];
                    if(t1 == t2)  ti = t1.first;
                }
                q2.pop();
            }
            i = ti;
        }
        lst[t1.second] = t1.first;
    }
    int sum = 0;
    for (int i = 1; i <= n; ++i)  sum += ta[i];
    stack<int> stk;
    while(q2.size()) {
        auto t2 = q2.top();
        q2.pop();
        while(stk.size()) {
            int t = stk.top();  stk.pop();
            int tmp = min(ta[t], t2.first - res);
            ta[t] -= tmp;
            if(ta[t]) {
                stk.push(t);
                break;
            }
        }
        int tmp = min(sum, t2.first - res);
        res += tmp;
        sum -= tmp;
        if(res < t2.first)  break;
        // if(q3.size()) {
        //     auto t3 = q3.top();
        //     if(t2.first == t3[0]) {
        //         q3.pop();
        //         res += t3[2];
        //         ta[t3[1]] = a[t3[1]] - t3[2];
        //         continue;
        //     }
        // }
        ta[t2.second] = a[t2.second];
        stk.push(t2.second);
    }
    for (int i = 1; i <= n; ++i)  res += ta[i];
    // assert(q2.size() > q3.size() || q2.size() + q3.size() == 0);
    cout << res << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);  cout.tie(0);
    int t = 1;  cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}