#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
#define all(x) (x).begin(), (x).end()
#define x first
#define y second
// #define endl "\n" 
#define int long long
// #define sz(x) ((int)(x).size())
#define lowbit(x) ((x) & -(x))
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i,x,y) for(int i = x;i<y;i++)
#define reb(i,x,y) for(int i = x;i<=y;i++)
typedef long long ll;
typedef pair<int, int> pii;
typedef double db;
typedef long double ld;
const int N = 1e5+10, M = 2e7+10, mod = 998244353 , inf = 0x7fffffff;
const ld eps = 1e-12;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}

struct fenwick {
    vector<int> tree;
    int sz;

    void add(int x, int d){
        if(!x)return;
        for(int i = x; i < sz; i += (i & -i)) tree[i] += d;
    }

    int sum(int x) {
        if (!x) return 0;
        if (x > sz) return -1;
        int res = 0;
        for (int i = x; i; i -= (i & -i)) res += tree[i];
        return res;
    }

    int sum(int x, int y){
        if(!x)return 0;
        return sum(y) - sum(x-1);
    }

    fenwick(int n): sz(n+1), tree(vector<int>(n+1)) {}
};


inline void solve() {
    int n, m;
    cin>>n>>m;
    vector<int>a(n+1);
    int s = 0;
    rep(i,1,n+1){
        cin>>a[i];
        s += a[i];
    }
    vector<pii>tar(m+1);
    int end = 0;
    rep(i,1,m+1){
        cin>>tar[i].x>>tar[i].y;
        end = tar[i].x;
    }

    map<int, int> rem;
    fenwick ud_tree(m+1);
    map<int,int> ud_x_to_idx;
    int ud_s = 0;
    int now = 0;
    for(int i = 1;i<=m;i++){
        int d = tar[i].x - now;
        if(d + ud_s > s)break;

        int ud_sum = ud_tree.sum(tar[i].y, i);
        int f = min({d+ud_sum, a[tar[i].y], tar[i].x-rem[tar[i].y]});
        
        int fx = d-f;
        // cout<<i<<" "<<fx<<" "<<ud_sum<<endl;
        ud_x_to_idx[tar[i].x] = i;
        if(fx > 0){
            ud_s += fx;
            ud_tree.add(i, fx);
        } else if(fx < 0){
            ud_s += fx;
            fx = abs(fx);
            int idx = ud_x_to_idx[rem[tar[i].y]];
            int hc = ud_tree.sum(idx, idx);
            // cout<<idx<<endl;
            while(idx <= i && hc <= fx && fx){
                if(hc==0){
                    idx++;
                    hc = ud_tree.sum(idx, idx);
                    continue;
                }
                ud_tree.add(idx, -hc);
                idx++;
                fx -= hc;
                hc = ud_tree.sum(idx, idx);
            }
            if(fx){
                ud_tree.add(idx, -fx);
                fx = 0;
            }
        }

        rem[tar[i].y] = tar[i].x;
        now = tar[i].x;
    }

    // cout<<ud_s<<endl;
    cout<<now + s - ud_s<<endl;
}

signed main(){
    IOS;
    cout << fixed << setprecision(10);
    int __ = 1;
    cin>>__;
    while(__--) {
        solve();
        // cout<<endl;
    }
    return 0;
}