#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
using i64 = long long;
const int inf = 1e18;
void solve()
{
    int n, k;
    cin >> n >> k;
    int sum = 0;
    vector<int> val(n + 1, 0);
    vector<int> a(n + 1, 0);
    vector<pair<int, int>> b(k + 2);
    vector<int> fa(n + 10, 0);
    vector<int> vis(max(n, k) + 10, 0);
    map<int, int> mp;
    priority_queue<int, vector<int>, greater<int>> q;

    for (int i = 1; i <= n; i++)
    {
        cin >> val[i];
        a[i] = val[i];
    }
    for (int i = 1; i <= k; i++)
    {
        cin >> b[i].first >> b[i].second;
    }
    b[k + 1] = {1e18, 0};

    for (int i = k + 1; i; i--)
    {
        fa[i] = mp[b[i].second];
        mp[b[i].second] = i;
        q.push(i);
        vis[b[i].second] = 1;
    }
    for (int i = 1; i <= n; i++)
    {
        if (!vis[i])
            sum += val[i];
    }
    int ans = 0;
    // cout << sum;
    for (int i = 1; i <= k + 1; i++)
    {
        int dis = b[i].first - b[i - 1].first;
        while (q.size())
        {
            int x = q.top();
            q.pop();
            if (a[b[x].second] < dis)
            {
                dis -= a[b[x].second];
                ans += a[b[x].second];
                a[b[x].second] = 0;
            }
            else
            {
                ans += dis;
                a[b[x].second] -= dis;
                if (x > i)
                    q.push(x);
                break;
            }
        }
        if (q.size())
        {
            // cout << i << '*' << endl;
            if (fa[i])
                q.push(fa[i]);
            else
                sum += val[b[i].second];
            a[b[i].second] = val[b[i].second];
            // cout << a[b[i].second] << '*' << endl;
        }
        else
        {
            // cout << "*" << dis << endl;
            sum -= dis;
            if (sum >= 0)
            {

                ans += dis;
                if (fa[i])
                    q.push(fa[i]);
                else
                    sum += val[b[i].second];
                a[b[i].second] = val[b[i].second];
            }
            else
            {
                ans += (sum + dis);
                cout << ans << '\n';
                return;
            }
        }
        // cout << ans << ' ' << a[1] << " " << a[2] << endl;
    }
}

signed main()
{
     ios::sync_with_stdio(false), cin.tie(0);
    int T = 1;
    cin >> T;
    while (T--)
        solve();
  
    return 0;
}