#include <bits/stdc++.h>

using namespace std;
using LL = long long;

void solved() {

    int n , m;
    cin >> n >> m;

    vector<int> a(n + 1);
    for(int i = 1 ; i <= n ; i ++ )
        cin >> a[i];

    auto c = a;

    vector<array<LL ,2>> b(m + 1);
    for(int i = 1 ; i <= m ; i ++ )
        for(int j = 0 ; j < 2 ; j ++ )
            cin >> b[i][j];
    map<int , int> mp;
    vector<int> nxt(m + 1 , m + 1);
    for(int i = m ; i ; i -- ){
        auto [x , t] = b[i];
        if(mp[t]){
            nxt[i] = mp[t];
        }
        mp[t] = i;
    }

    LL sum = 0;
    priority_queue<array<LL , 2> , vector<array<LL , 2>> , greater<array<LL , 2>>> q;
    for(int i = 1 ; i <= m ; i ++ )
        if(mp[b[i][1]] == i){
            q.push({i , b[i][1]});
        }
    for(int i = 1 ; i <= n ; i ++ )
        if(!mp[i]) sum += a[i];

    LL ans = 0;
    for(int i = 1 ; i <= m ; i ++ ){
        LL s = b[i][0] - b[i - 1][0];

        while(s && !q.empty()){
            auto [x , j] = q.top();
            q.pop();

            if(s >= a[j]) s -= a[j] , a[j] = 0;
            else {
                s = 0;
                a[j] -= s;
                if(j != b[i][1]) q.push({x , j});
            }
        }

        if(s > sum){
            cout << b[i][0] - s << "\n";
            return ;
        }
        sum -= s;
        q.push({nxt[i] , b[i][1]});
        a[b[i][1]] = c[b[i][1]];
    }

    ans = b[m][0] + sum;
    while(!q.empty()){
        auto [x , y]  = q.top();
        q.pop();

        ans += a[y];
    }

    cout << ans << "\n";
}

int main(){

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    cin >> t;

    while(t -- )
        solved();

    return 0;
}