#include <bits/stdc++.h>

using namespace std;

typedef double ld;
typedef unsigned long ul;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;

const int maxn = 2e6 + 50;
const ll inf = 0x3f3f3f3f3f3f;

ll a[maxn], b[maxn], x[maxn], t[maxn];

void solve() {
  ll n, m, ans = 0ll;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    b[i] = a[i];
    ans += a[i];
  }

  map<ll, ll> dic;
  map<ll, set<ll>> mp;
  for (int i = 1; i <= m; i++) {
    cin >> x[i] >> t[i];
    dic[x[i]] = t[i]; // 位置x[i]的可以给t[i]充电
    mp[t[i]].insert(x[i]);
  }

  if (x[1] > ans) {
    cout << ans << '\n';
    return;
  }

  set<ll> st;
  for (int i = 1; i <= n; i++) {
    if (mp.count(i) && !mp[i].empty()) {
      st.insert(*mp[i].begin());
    }
  }

  ll sum = ans;
  for (int i = 1; i <= m; i++) {
    auto pos = *st.begin();                  // 下一个油站的位置
    ll dis = x[i] - x[i - 1], ti = dic[pos]; // 需要的油量和油类型
    set<ll> nst;
    while (dis && !st.empty()) {
      if (dis < b[ti]) {
        b[ti] -= dis;
        dis = 0;
      } else {
        // 用完t的油,并使用下一个油箱
        dis -= b[ti];
        b[ti] = 0;
        st.erase(pos);
        mp[ti].erase(pos);
        if (!mp[ti].empty()) {
          nst.insert(*mp[ti].begin());
        }
        if (!st.empty()) {
          pos = *st.begin();
          ti = dic[pos];
        }
      }
    }

    // 删去浪费的部分
    while (!st.empty() && *st.begin() <= x[i]) {
      pos = *st.begin(), ti = dic[pos];
      st.erase(pos);
      mp[ti].erase(pos);
      b[ti] = 0ll;
      if (!mp[ti].empty()) {
        nst.insert(*mp[ti].begin());
      }
    }

    while (!nst.empty()) {
      st.insert(*nst.begin());
      ti = dic[*nst.begin()];
      b[ti] = a[ti];
      nst.erase(nst.begin());
    }

    if (dis) {
      // 使用最初的油
      if (sum >= dis) {
        sum -= dis;
        dis = 0;
      }
    }
    if (!dis)
      break;
    ans = max(ans, x[i] + sum);
  }

  cout << ans << '\n';
}

/*
1
3 5
3 3 3
8 1
10 2
11 1
13 2
16 3

23

2
3 1
3 3 3
8 1
2 2
5 2
1 2
2 1

9
7
*/

void init() {
  // init_primes();
}

int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  init();
  int _t = 1;
  cin >> _t;
  cin.get();
  while (_t--)
    solve();

  return 0;
}