#include <bits/stdc++.h>
#define lson (nw << 1)
#define rson (nw << 1 | 1)
using namespace std;
typedef long long ll;
inline ll read() {
ll x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
} return x * f;
}
const int N = 2e5 + 10;
int n, m; ll a[N], c[N], x[N], t[N];
vector<int> b[N]; int ps[N];
void init() {
for (int i = 1; i <= n; i++) b[i].clear(), ps[i] = 0;
for (int i = 1; i <= n +m ; i++) c[i] = 0;
}
struct Seg {
ll d; bool f;
}tr[N*4];
void pushup(int nw) {
tr[nw].d = tr[lson].d + tr[rson].d;
}
void build(int nw, int l, int r) {
tr[nw].f = 0; tr[nw].d = 0;
if (l == r) {
tr[nw].d = c[l]; return;
} int mid = (l + r) >> 1;
build(lson, l, mid); build(rson, mid + 1, r);
pushup(nw);
}
void pushdown(int nw) {
if (tr[nw].f) {
tr[lson].f = tr[rson].f = 1;
tr[lson].d = tr[rson].d = 0;
tr[nw].f = 0;
}
}
void update(int nw, int l, int r, int x, int y) {
if (x <= l && r <= y) {
tr[nw].f = 1; tr[nw].d = 0; return;
} int mid = (l + r) >> 1; pushdown(nw);
if (x <= mid) update(lson, l, mid, x, y);
if (y > mid) update(rson, mid + 1, r, x, y);
pushup(nw);
}
void add(int nw, int l, int r, int x, ll d) {
if (l == r) {
tr[nw].d += d; return;
} int mid = (l + r) >> 1; pushdown(nw);
if (x <= mid) add(lson, l, mid, x, d);
else add(rson, mid + 1, r, x, d);
pushup(nw);
}
ll ask(int nw, int l, int r, int x, int y) {
if (x <= l && r <= y) {
return tr[nw].d;
} int mid = (l + r) >> 1; pushdown(nw); ll ans = 0;
if (x <= mid) ans += ask(lson, l, mid, x ,y);
if (y > mid) ans += ask(rson, mid + 1, r ,x ,y);
return ans;
}
int findl(int nw, int l, int r, ll d) {
if (l == r) return l;
pushdown(nw);
ll ls = tr[lson].d; int mid = (l + r) >> 1;
if (ls <= d) {
return findl(rson, mid + 1, r, d - ls);
}
return findl(lson, l, mid, d);
}
void solve() {
n = read(), m = read(); init();
for (int i = 1; i <= n; i++) a[i] = read();
for (int i = 1; i <= m; i++) {
x[i] = read(); t[i] = read();
b[t[i]].push_back(i);
} int r = m;
for (int i = 1; i <= n; i++) {
ps[i] = 0;
if (!b[i].size()) {
++r; c[r] = a[i];
} else {
c[b[i][0]] = a[i];
}
}
build(1, 1, r); x[m+1] = 1e18;
for (int i = 1; i <= m + 1; i++) {
ll d = x[i] - x[i-1];
if (tr[1].d < d) {
printf("%lld\n", x[i-1] + tr[1].d); return;
}
int p = findl(1, 1, r, d); ll las = d - ask(1, 1, r, 1, p);
update(1, 1, r, 1, p);
if (p + 1 <= r) add(1, 1, r, p + 1, -las);
int nw = t[i]; update(1, 1, r, b[nw][ps[nw]], b[nw][ps[nw]]); ps[nw]++;
if (ps[nw] < b[nw].size()) {
add(1, 1, r, b[nw][ps[nw]], a[nw]);
}
}
}
int main() {
int t = read();
while (t--) {
solve();
}
return 0;
}
/*
2
3 1
3 3 3
8 1
2 2
5 2
1 2
2 1
*/