// #pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
#define pb push_back
#define st first
#define nd second
#define PII pair<ll, ll>
#define D(x, y) cout << x << "=" << y << endl;
#define fcout(x, n) cout << fixed << setprecision(x) << n << endl;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define rep2(i, a, b) for (int i = a; i >= b; i--)
// #define int long long
// #define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
const ll inf = 0x3f3f3f3f;
const int N = 1e6 + 10;
const int M = 1e9+7;
inline ll read()
{
    ll x = 0;
    bool f = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar())
        if (c == '-')
            f = 0;
    for (; isdigit(c); c = getchar())
        x = (x << 3) + (x << 1) + c - '0';
    return f ? x : 0 - x;
}
inline void out(ll x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        out(x / 10);
    putchar(x % 10 + '0');
}
// __int128 rd()
// {
// 	char arr[30];
// 	__int128 res = 0;
// 	scanf("%s", arr);
// 	for (int i = 1; i <= strlen(arr); i++)
// 	{
// 		res *= 10;
// 		res += arr[i]-'0';
// 	}
// 	return res;
// }
// void pt(__int128 num)
// {
// 	if (num > 9) pt(num / 10);
// 	putchar(num % 10 + '0');
// }

ll n, m;
ll a[N];
ll d[N];
vector< PII >v;
void solve()
{
    cin>>n>>m;
    memset(d,0,sizeof(d));
    queue<ll>q[n+5];
    rep(i,1,n+1) cin>>a[i];
    rep(i,0,m)
    {
        ll x,y;cin>>x>>y;
        v.pb({x,y});q[y].push(x);
    }
    rep(i,1,n+1) q[i].push(inf);
    sort(v.begin(),v.end());
    priority_queue<PII,vector<PII>,greater<PII> >qr,qr1;
    rep(i,1,n+1)
    {
        qr.push({q[i].front(),i});q[i].pop();
    }
    ll ans=0;
    rep(i,0,m)
    {
        ll x=v[i].st-ans;
        while(x!=0)
        {//D("x",x);
            if(!qr.empty())
            {
                if(a[qr.top().nd]-d[qr.top().nd]<=x)
                {
                    if(qr.top().st!=inf) qr1.push(qr.top());
                    x-=a[qr.top().nd]-d[qr.top().nd];
                    d[qr.top().nd]=0;qr.pop();
                }
                else 
                {
                    d[qr.top().nd]+=x;
                    break;
                }
            }
            else return cout<<ans+v[i].st-x<<endl,void();
        }//D("d",d[qr.top().nd]);
        if(qr1.empty()) d[qr.top().nd]=0;
        else
        {
            ll t=qr1.top().nd;
            if(!q[t].empty())
            {
                qr.push({q[t].front(),t});
                q[t].pop();
            }
            qr1.pop();
        }
        ans=v[i].st;
    }
    while(!qr.empty()) 
    {
        ans+=a[qr.top().nd]-d[qr.top().nd];
        qr.pop();
    }
    cout<<ans<<endl;
}
signed main()
{
    IOS
        // freopen("../.vscode/io/in.txt","r",stdin),freopen("../.vscode/io/out.txt","w",stdout);
        ll T = 1;
    cin >> T;
    while (T--)
        solve();
}