#include<iostream>
#include<cstring>
#include<vector>
#include<set>
using namespace std;
using LL = long long;

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T;
    cin >> T;
    while(T--){
        int n, m;
        cin >> n >> m;
        vector<int> a(n + 1);
        for(int i = 1; i <= n; i++) cin >> a[i];
        vector<LL> x(m + 1);
        vector<int> t(m + 1);
        for(int i = 1; i <= m; i++){
            cin >> x[i] >> t[i];
        }

        auto check = [&](LL mid){
            vector<int> last(n + 1, m + 1);
            int pos = m;
            while(mid <= x[pos]) pos--;
            vector<LL> s1(m + 1), s2(m + 1);
            for(int i = pos; i >= 0; i--){
                LL len = mid - x[i];
                s1[i] += len;
                if (i == 0){
                    for(int j = 1; j <= n; j++){
                        s2[last[j] - 1] += a[j];
                    }
                }
                else{
                    s2[last[t[i]] - 1] += a[t[i]];
                }
                last[t[i]] = i;
                mid = x[i];
            }
            LL remain = 0;
            for(int i = m; i >= 0; i--){
                if (s2[i] + remain < s1[i]){
                    return false;
                }
                remain = s2[i] + remain - s1[i];
            }
            return true;
        };

        LL l = 0, r = 1e15;
        while(l < r){
            LL mid = (l + r + 1) / 2;
            if (check(mid)) l = mid;
            else r = mid - 1;
        }
        cout << r << '\n';
    }

}