#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define PII pair<ll, ll>
const ll mod = 1e9 + 7;
const ll MAXN = 500005;
const ll base1 = 131;
const ll base2 = 127;
ll _ = 1, n, m;
void solve()
{
    cin >> n >> m;
    vector<ll> a(n + 100, 0);
    vector<ll> v(n + 100, 0);
    vector<ll> x(m + 100, 0);
    vector<ll> t(m + 100, 0);
    vector<queue<ll>> cd(n + 10);
    ll sum = 0, ans = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        v[i] = a[i];
    }
    for (int i = 1; i <= m; i++)
    {
        cin >> x[i] >> t[i];
        cd[t[i]].push(x[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        cd[i].push(1e18);
    }
    ans = 0;
    priority_queue<PII, vector<PII>, greater<PII>> q;
    for (int i = 1; i <= n; i++)
    {
        if (cd[i].size() > 0)
        {
            ll s = cd[i].front();
            cd[i].pop();
            q.emplace(s, i);
        }
    }
    for (int i = 1; i <= m; i++)
    {
        ll len = x[i] - x[i - 1];
        while (len > 0)
        {
            if (!q.empty())
            {
                auto [x1, i1] = q.top();
                q.pop();
                if (v[i1] == 0)
                {
                    continue;
                }
                if (v[i1] > len)
                {
                    v[i1] -= len;
                    len = 0;
                    q.emplace(x1, i1);
                    break;
                }
                else if (v[i1] <= len)
                {
                    len -= v[i1];
                    v[i1] = 0;
                }
            }
            else
            {
                break;
            }
        }
        if (len > 0)
        {
            ans += (x[i] - x[i - 1]) - len;
            break;
        }
        else
        {
            v[t[i]] = a[t[i]];
            ll fi = 1e18, ti = t[i];
            if (cd[t[i]].size() > 0)
            {
                fi = cd[t[i]].front();
                cd[v[i]].pop();
            }
            if (!q.empty())
            {
                if (q.top().second == ti)
                {
                    q.pop();
                }
                q.emplace(fi, ti);
            }
            ans += x[i] - x[i - 1];
        }
    }
    for (int i = 1; i <= n; i++)
    {
        ans += v[i];
    }
    cout << ans << '\n';
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> _;
    while (_--)
    {
        solve();
    }
    return 0;
}
// 最少走sum
// 遇到一个加油站时，
// sum a[i] t;
// ans+x;
//