#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define int long long
void solve(){
    int n,m;
    cin>>n>>m;
    vector<int> a(n+1);
    int sum=0;
    for(int i=1;i<=n;i++)cin>>a[i],sum+=a[i];
    vector<pair<int,int>> b(m+1);
    for(int i=1;i<=m;i++){
        cin>>b[i].x>>b[i].y;
    }
    auto check = [&](int x){
        int t=0,s=sum;
        for(int i=1;i<=m;i++){
            if(t+s>=b[i].x){
                s-=b[i].x-b[i-1].x;
                t+=b[i].x-b[i-1].x;
                s+=min(b[i].x-b[i-1].x,a[b[i].y]);
            }
            else {
                t+=s;
                s=0;
                break;
            }
        }
        t+=s;
        if(t>=x)return 0;
        return 1;
    };
    int l=1,r=1e18;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    cout<<l-1<<"\n";
}
signed main(){
    cin.tie(0)->ios::sync_with_stdio(0);
    cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)solve();
}