#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define int long long
// #define int __int128
#define re read()
#define pr(x) print(x)
#define fup(a, b, c, d) for(int a = (b); a <= (c); a += (d))
#define fdo(a, b, c, d) for(int a = (b); a >= (c); a -= (d))
typedef long long ll;
typedef pair<int , int> PII;
typedef map<int , int> MII;
const int inf = 0x3f3f3f3f, N = 2e6 + 10, M = 4e5 + 10, mod = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;




void solve()
{
    int n, m, ssu = 0;
    cin >> n >> m;
    vector<int> a(n + 10);
    map<int , int> mp;

    fup(i, 1, n, 1) {
        cin >> a[i];
        ssu += a[i];
    }

    vector<PII> v(m + 10);
    vector<int> b(m + 10);
    fup(i, 1, m, 1) {
        int x, y;
        cin >> x >> y;
        v[i] = {x, y};
    }

    fup(i, 1, m, 1) {
        b[i] = v[i].first - v[i - 1].first;
    }

    vector<int> nxt(n + 10), la(n + 10);

    fup(i, 1, m, 1) nxt[i] = i;
    // cout << b[1] << '\n';
    fup(i, 1, m, 1) {
        int op = v[i].second;
        int nu = a[op], su = 0, f = 0;
        fup(j, la[op], i, 1) {
            if(su + b[j] <= nu) {
                b[j] = 0;
            }
            else {
                b[j] -= (nu - su);
                // cout << j << ' ' << b[j] << '\n';
                f = j;
                break ;
            }
            su += b[j];
            j = nxt[j];
        }
        if(!f) f = i;
        fup(j, la[op], f, 1) {
            nxt[j] = f;
        }
        la[op] = i + 1;
    }
    // cout << '\n';

    int an = 0;
    fup(j, 1, m, 1) {
        // cout << b[j] << ' ';
        if(an + b[j] > ssu - a[v[j].second]) {
            cout << v[j - 1].first + (ssu - an) << '\n';
            return ;
        }
        an += b[j];
    }
    // cout << "\n";
    // cout << ssu << ' ' << an << '\n';

    cout << v[m].first + (ssu - an) << '\n';
}

signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int _ = 1;
    cin >> _;
    while(_ --)
    {
        solve();
    }
    // fup(i, 1, _, 1) {
    //     if(i == 16 && _ == 1000) {
    //         // cout << "1238715\n";
    //         int n, m, su = 0, ssu;
    //         cin >> n >> m;
    //         // cout << n << ' ' << m << " : ";
    //         vector<int> a(n + 10);
    //         map<int , int> mp;

    //         fup(i, 1, n, 1) {
    //             cin >> a[i];
    //             // cout << a[i] << ' ';
    //             su += a[i];
    //         }
    //         // cout << " : ";
    //         ssu = su;

    //         vector<PII> v(m + 10);
    //         fup(i, 1, m, 1) {
    //             int x, y;
    //             cin >> x >> y;
    //             if(i > 12) cout << x << ' ' << y << " , ";
    //             v[i] = {x, y};
    //         }
    //         continue ;
    //     }
    //     solve();
    // }
}