#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
typedef pair<int,int> PII;
const int N=1e5+10;
const int inf=1e18;
int a[N];
PII xt[N];
int res,ans;
int n,m;
bool check(int mid)
{
    if(res>=mid)
    {
        return true;
    }
    int res1=res;
    for(int i=m;i>=1;i--)
    {
        if(xt[i].first>mid)
        {
            continue;
        }
        if(xt[i].first-xt[i-1].first>a[xt[i].second])
        {
            res1+=a[xt[i].second];
        }
        else
        {
            res1+=(xt[i].first-xt[i-1].first);
        }
    }
    if(res1>=mid)
    {
        return true;
    }
    return false;
}
void solve()
{
    ans=0;
    res=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        res+=a[i];
    }
    xt[0].first=0;
    for(int i=1;i<=m;i++)
    {
        cin>>xt[i].first>>xt[i].second;
    }
    sort(xt+1,xt+1+m);
    int l=1,r=inf;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(check(mid))
        {
            ans=max(mid,ans);
            l=mid+1;
        }
        else
        {
            r=mid-1;
        }
    }
    cout<<ans<<endl;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    int t;
	while(cin>>t)
	{
        while(t--)
        {   
            solve();
        }
    }
}