#include<bits/stdc++.h>

using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using f64 = long double;
using i128 = __int128;
using u128 = unsigned __int128;
using f128 = __float128;

#ifndef ONLINE_JUDGE
#include "algo/debug.hpp"
#else
#define debug(...) (void)42
#endif

template<class T>
constexpr void chmax(T& x, T y) {
    if (y > x) {
        x = y;
    }
}

template<class T>
constexpr void chmin(T& x, T y) {
    if (y < x) {
        x = y;
    }
}

auto main() ->int32_t {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout << std::fixed << std::setprecision(13);

    auto solve = [&]() {
    	int n, m;
    	std::cin >> n >> m;

    	std::vector<int>a(n + 1);
    	for (int i = 1; i <= n; i += 1) {
    		std::cin >> a[i];
    	}

    	std::vector<int>x(m + 1),t(m + 1);
    	for (int i = 1; i <= m; i += 1) {
    		std::cin >> x[i] >> t[i];
    	}

    	std::vector<std::vector<int>>adj(n + 1);
    	for (int i = m; i >= 1; i -= 1) {
    		adj[t[i]].push_back(x[i]);
    	}

    	i64 ext = 0, all = 0;
    	std::priority_queue<std::array<int, 2>, std::vector<std::array<int, 2>>, std::greater<>>q;
    	for (int i = 1; i <= n; i += 1) {
    		if (adj[i].empty()) {
    			ext += a[i];
    		} else {
    			q.push({adj[i].back(),a[i]});
    			all += a[i];
    		}
    	}

    	for (int i = 0; i < m; i += 1) {
    		int d = x[i + 1] - x[i];
    		if (all >= d) {
    			while (d > 0) {
    				auto [x, y] = q.top();
    				q.pop();
    				d -= y;
    				all -= y;
    			}
    			if (not adj[t[i]].empty()) {
    				adj[t[i]].pop_back();
    			}
    			if (not adj[t[i]].empty()) {
    				all += a[t[i]];
    				q.push({adj[t[i]].back(),a[t[i]]});
    			} else {
    				ext += a[t[i]];
    			}
    		} else if (all + ext >= d) {
    			while (not q.empty()) {
    				auto [x, y] = q.top();
    				q.pop();
    				d -= y;
    				all -= y;
    			}
    			ext -= d;
    			if (not adj[t[i]].empty()) {
    				adj[t[i]].pop_back();
    			}
    			if (not adj[t[i]].empty()) {
    				all += a[t[i]];
    				q.push({adj[t[i]].back(),a[t[i]]});
    			} else {
    				ext += a[t[i]];
    			}
    		} else {
    			std::cout << x[i] + all + ext << '\n';
    			return ;
    		}
    	}

    	std::cout << x.back() + all + ext << '\n';
    };

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}