#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 = 1; i <= n; ++i)  q1.push({1e15, i});
    for (int i = 0; q1.size() != 0 ; res = i) {
        auto t1 = q1.top();
        q1.pop();
        q2.push(t1);
        if(ta[t1.second] == 0)  q3.push({lst[t1.second], t1.first, t1.second});
        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();
                        q1.push({t3[1], t3[2]});
                        ta[t1.second] = ti - t1.first;
                        ti = t1.first;
                        if(ta[t1.second])  q1.push(t1);
                        break;
                    }
                    else  ta[t2.second] = a[t2.second];
                }
                else {
                    ta[t2.second] = a[t2.second];
                    if(t1 == t2)  ti = t1.first;
                }
                q2.pop();
            }
            i = ti;
        }
        lst[t1.second] = t1.first;
    }
    // for (int i = 1; i <= n; ++i)  res += ta[i];
    // while(q2.size()) {
    //     auto t2 = q2.top();
    //     if(res < t2.first)  break;
    //     q2.pop();
    //     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];
    //         }
    //         else  res += a[t2.second];
    //     }
    //     else  res += a[t2.second];
    // }
    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;
}