#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, n + 1);
            int pos = m;
            while(mid <= a[pos]) pos--;
            LL remain = 0;
            set<pair<int, LL> > s;
            for(int i = pos; i >= 0; i--){
                LL len = mid - x[i];
                remain += len;
                s.insert({i, len});
                if (i == 0){
                    for(int j = 1; j <= n; j++){
                        LL k = a[j];
                        while(k and !s.empty()){
                            auto it = s.upper_bound({last[j], 0});
                            if (it == s.begin()) break;
                            auto [x, y] = *--it;
                            if (y > k){
                                s.erase({x, y});
                                s.insert({x, y - k});
                                remain -= k;
                                k = 0;
                            }
                            else{
                                remain -= y;
                                k -= y;
                                s.erase({x, y});
                            }
                        }
                    }
                }
                else{
                    LL k = a[t[i]];
                    while(k and !s.empty()){
                        auto it = s.upper_bound({last[t[i]], 0});
                        if (it == s.begin()) break;
                        auto [x, y] = *--it;
                        if (y > k){
                            s.erase({x, y});
                            s.insert({x, y - k});
                            remain -= k;
                            k = 0;
                        }
                        else{
                            remain -= y;
                            k -= y;
                            s.erase({x, y});
                        }
                    }
                }
                last[t[i]] = i;
                mid = x[i];
            }
            return remain == 0;
        };

        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';
    }

}