#include<bits/stdc++.h>
using namespace std;
using i64 = __int128;

ostream& operator<<(ostream&out, __int128 x){
    vector<char> st;
    do{
        st.emplace_back((x % 10) + '0');
    }while(x /= 10);
    while(!st.empty()){
        out << st.back();
        st.pop_back();
    }
    return out;
}

int lowbit(int x){return x&-x;}
struct BIT{
    int n;
    std::vector<i64> node;
    BIT(int n=0){init(n);}
    void init(int n){
        this->n = n;
        node.assign(n+1, 0ll);
    }
    void add(int k, i64 v){
        if(!k){
            node[k] += v;
        }else{
            for(;k<=n;k+=lowbit(k))node[k]+=v;
        }
    }
    i64 ask(int k){
        i64 ret = node[0];
        for(;k>0;k-=lowbit(k))ret+=node[k];
        return ret;
    }
    i64 ask(int l, int r){
        if(l>r)std::swap(l,r);
        return ask(r) - ask(l-1);
    }
    int kth(i64 v) {
        int now = 0;
        for(int i=19;i>=0;i--) {
            now += 1<<i;
            if(now > n || node[now] >= v) now -= 1<<i;
            else v -= node[now];
        }
        return now + 1;
    }
};

struct maxBIT{
    int n;
    std::vector<int> node;
    maxBIT(int n=0){init(n);}
    void init(int n){
        this->n = n;
        node.assign(n+1, 0ll);
    }
    void set(int k, int v){
        if(!k){
            node[k] = max(node[k], v);
        }else{
            for(;k<=n;k+=lowbit(k)) node[k] = max(node[k], v);
        }
    }
    int ask(int k){
        int ret = node[0];
        for(;k>0;k-=lowbit(k)) ret = max(ret, node[k]);
        return ret;
    }
};

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; cin >> T;
    while(T--){
        int n, m; cin >> n >> m;
        i64 sum = 0;
        vector<int> a(n);
        for(auto&x : a){
            cin >> x;
            sum += x;
        }
        vector<pair<int, int>> b(m);
        for(auto&[x, t] : b){
            cin >> x >> t; t--;
        }
        // sort(b.begin(), b.end());

        BIT usage(m);
        maxBIT maxi(m);
        usage.add(0, -sum);

        i64 ans = 0;
        unordered_map<int, int> last;
        for(int i=0, y=0; i<m; i++){
            auto[x, t] = b[i];
            auto d = x - y;
            if(usage.ask(i + 1) + d > 0){
                break;
            }
            usage.add(i + 1, d);
            ans += d;
            last[t] = max(last[t], maxi.ask(last[t]));
            auto last_usage = usage.ask(last[t] + 1, i + 1);
            auto restore = min<i64>(last_usage, a[t]);
            auto pos = usage.kth(usage.ask(last[t]) + restore);
            auto prev = usage.ask(last[t] + 1, pos - 1); 
            usage.add(pos, prev - restore);
            usage.add(last[t] + 1, - prev);
            maxi.set(last[t], pos - 1);
            last[t] = i + 1;
            y = x;

            // cout << format("[{}] ans:{}\n", i, ans);
            // cout << format("[{}] usage:{}\n", i, usage.ask(i + 1));
        }
        ans -= usage.ask(m);
        cout << ans << '\n';
    }

    return 0;
}