#include <bits/stdc++.h>
#define int int64_t

using std::cin;
using std::cout;
const char endl = '\n';

void solve() {
  int n, m;
  cin >> n >> m;
  std::vector<int> a(n + 1), res(n + 5);
  int sum = 0;
  for (int i = 1; i <= n; ++i) cin >> a[i], sum += a[i], res[i] = a[i];
  std::vector<int> x(m + 5), t(m + 5);
  std::vector<std::queue<int>> charge(n + 1);
  for (int j = 1; j <= m; ++j) {
    cin >> x[j] >> t[j];
    charge[t[j]].push(x[j]);
  }
  x[m + 1] = (int)1E18;
  for (int i = 1; i <= n; ++i) { charge[i].push((int)1E18); }
  std::vector<int> last(n + 1);
  std::priority_queue<std::pair<int, int>> q; 
  for (int i = 1; i <= n; ++i) {
    q.push({-charge[i].front(), i});
    charge[i].pop();
  }
  for (int i = 1; i <= m + 1; ++i) {
    std::queue<int> used;
    int d = x[i] - x[i - 1];
    while (!q.empty()) {
      auto [xj, tj] = q.top();
      xj *= -1;
      if(xj < x[i]) {
        q.pop();
        if(charge[tj].size()) {
          q.push({-charge[tj].front(), tj});
          charge[tj].pop();
        }
        continue;
      }
      // std::cerr << xj << " " << tj << '\n';
      if (d < res[tj]) {
        res[tj] -= d;
        d = 0;
        break;
      } else {
        d -= res[tj];
        res[tj] = 0;
        used.push(tj);
        q.pop();
      }
    }
    if (d > 0) {
      cout << x[i] - d << endl;
      return;
    }
    res[t[i]] = a[t[i]];
    while (!used.empty()) {
      int u = used.front();
      if (charge[u].size()) {
        q.push({-charge[u].front(), u});
        charge[u].pop();
      }
      used.pop();
    }
  }

  // auto [xj, tj] = q.top();
  // q.pop();
  // if (last[tj] <= ans)
  //   ans += std::min(a[tj], xj - last[tj]);
  // else
  //   q.push({charge[tj].front(), tj});
  // charge[tj].pop();
}

int32_t main() {
#ifndef _DEBUG
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
#endif
  int tc = 1;
  std::cin >> tc;
  while (tc--) solve();
#ifdef _DEBUG
  std::cout << std::endl;
  std::cout << "Time used: " << clock() << "ms" << std::endl;
  system("pause");
  return 0;
#endif
}