#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> PII;
#define endl "\n"
#define ft first
#define sd second
#define pb push_back
const int MOD = 1e9 + 7;
int n,m;
const int N = 1e5 + 10;
int a[N],c[N];
PII b[N];
void solve() {
    cin>>n>>m;
    for(int i = 1;i <= n;i++){
        cin>>a[i];
        c[i] = a[i];
    }
    vector<int> v[n + 1];
    for(int i = 1;i <= m;i++)
    {
        cin>>b[i].ft>>b[i].sd;
        v[b[i].sd].pb(b[i].ft);
    }
    priority_queue<PII,vector<PII>,greater<PII>> nxt,all;
    for(int i = 1;i <= n;i++){
        v[i].pb(1e18);
        sort(v[i].begin(),v[i].end(),greater<int>());
        for(int x : v[i])
            all.push({x,i});
    }
    for(int i = 1;i <= n;i++){
        nxt.push({v[i].back(),i});
        v[i].pop_back();
    }
    int now = 0;
    auto check = [&]()->bool
    {
//        cout << "check" << endl;
//        cout<<nxt.empty()<<endl;
        if(nxt.empty())
        {
            return false;
        }
//        cout<<nxt.empty()<<endl;
//        cout<<now<<endl;
        auto t = nxt.top();
        int dist1 = a[t.sd],dist2 = t.ft - now;
        now +=min(dist1,dist2);
        a[t.sd] -=min(dist1,dist2);
//        cout<<"ok"<<endl;
        if(a[t.sd] == 0 || now >= t.ft){
            nxt.pop();
        }
        auto tt = all.top();
        if(tt.ft <= now){
            a[tt.sd] = c[tt.sd];
            all.pop();
            
            nxt.push({v[tt.sd].back(),tt.sd});
            v[tt.sd].pop_back();
            }
        }
        return true;
    };
    while(check());
    cout<<now<<endl;
    return ;
}
signed main() {
//    ios::sync_with_stdio(0);
//    cin.tie(0);
//    cout.tie(0);
    int T = 1;
    cin>>T;
    while(T--)
        solve();
    return 0;
}
/*
2
3 1
3 3 3
8 1
2 2
5 2
1 2
2 1


1
3 2
2 2 2
6 1
7 1

 1
3 3
1 2 4
5 1
8 3
11 3

 */

answer.code: In function ‘void solve()’:
answer.code:65:9: error: expected ‘,’ or ‘;’ before ‘return’
   65 |         return true;
      |         ^~~~~~
answer.code: At global scope:
answer.code:67:5: error: expected unqualified-id before ‘while’
   67 |     while(check());
      |     ^~~~~
answer.code:68:5: error: ‘cout’ does not name a type
   68 |     cout<<now<<endl;
      |     ^~~~
answer.code:69:5: error: expected unqualified-id before ‘return’
   69 |     return ;
      |     ^~~~~~
answer.code:70:1: error: expected declaration before ‘}’ token
   70 | }
      | ^