#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(0), cin.tie(0)
#define time chrono::system_clock::now().time_since_epoch().count()
using namespace std;
#define int long long
using ll = long long;
using pll = pair<int, int>;
#define endl '\n'

const int mod = 1e9 + 7, N = 2e5 + 10;

void solve(){
    int n,m;
    cin>>n>>m;
    vector<int> a(n+10),b(m+10),c(m+10);
    vector<int> pos[n+10],now(n+10,0);
    int sum=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    multiset<pair<int,int>> q;
    for(int i=1;i<=m;i++){
        cin>>b[i]>>c[i];
        pos[c[i]].push_back(i);
        if(pos[c[i]].size()==1)q.insert({i,c[i]});
    }

    for(int i=1;i<=n;i++){
        if(!pos[i].size())q.insert({m+i,i});
        pos[i].push_back(n+m+1);
    }

    int cnt=1;
    int dis=b[cnt]-b[cnt-1];
    int ans=0;
    while(sum>=dis&&cnt<=m){
        ans+=dis;
        sum-=dis;
        while(dis&&q.size()){
            int id=(*q.begin()).first;
            int x=(*q.begin()).second;
            int mi=(dis,a[x]);
            dis-=mi;
            a[x]-=mi;
            if(x==c[cnt])sum+=mi;
            q.erase(q.begin());
            if(pos[x][now[x]]!=n+m+1){
                now[x]++;
                q.insert({pos[x][now[x]],x});
            }
        }
        cnt++;
        dis=b[cnt]-b[cnt-1];
    }
    if(sum){
        ans+=sum;
    }
    cout<<ans<<endl;
}

signed main()
{
    ios;
    int t = 1;
    cin >> t;
    while (t--)
        solve();
    return 0;
}