#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define endl '\n'
#define dbg(x) cerr<<"In Line "<<__LINE__<<' '<<#x<<" = "<<(x)<<endl
int a[100005],x[100005],t[100005],b[100005],nxt[100005],to[100005];
struct cmp{
	bool operator ()(int x,int y){
		if(!b[x]||!b[y]) return b[x];
		if(nxt[x]^nxt[y]) return nxt[x]<nxt[y];
		return x<y;
	}
};
int main(){
	cin.tie(0)->sync_with_stdio(0);
	int T;cin>>T;
	while(T--){
		int n,m;cin>>n>>m;
		for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
		set<int,cmp> s;
		for(int i=1;i<=m;i++) cin>>x[i]>>t[i];
		for(int i=1;i<=n;i++) nxt[i]=m+1;
		for(int i=m;i;i--) to[i]=nxt[t[i]],nxt[t[i]]=i;
		for(int i=1;i<=n;i++) s.emplace(i);
		bool no=0;
		for(int i=1;i<=m;i++){
			int now=x[i]-x[i-1];
			while(now){
				int it=*s.begin();
				s.erase(it);
				if(b[it]<now){
					if(!b[it]) break;
					now-=b[it],b[it]=0;
				}
				else b[it]-=now,now=0;
				s.emplace(it);
			}
			s.erase(t[i]),b[t[i]]=a[t[i]],nxt[t[i]]=to[i],s.emplace(t[i]);
			if(now){
				cout<<x[i]-now<<endl,no=1;
				break;
			}
		}
		if(!no){
			ll ans=x[m];
			for(int i=1;i<=n;i++) ans+=b[i];
			cout<<ans<<endl;
		}
	}
}

In file included from /usr/include/c++/13/map:62,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:152,
                 from answer.code:1:
/usr/include/c++/13/bits/stl_tree.h: In instantiation of ‘static const _Key& std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_S_key(_Const_Link_type) [with _Key = int; _Val = int; _KeyOfValue = std::_Identity<int>; _Compare = cmp; _Alloc = std::allocator<int>; _Const_Link_type = const std::_Rb_tree_node<int>*]’:
/usr/include/c++/13/bits/stl_tree.h:2118:47:   required from ‘std::pair<std::_Rb_tree_node_base*, std::_Rb_tree_node_base*> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_get_insert_unique_pos(const key_type&) [with _Key = int; _Val = int; _KeyOfValue = std::_Identity<int>; _Compare = cmp; _Alloc = std::allocator<int>; key_type = int]’
/usr/include/c++/13/bits/stl_tree.h:2435:15:   required from ‘std::pair<std::_Rb_tree_iterator<_Val>, bool> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_emplace_unique(_Args&& ...) [with _Args = {int&}; _Key = int; _Val = int; _KeyOfValue = std::_Identity<int>; _Compare = cmp; _Alloc = std::allocator<int>]’
/usr/include/c++/13/bits/stl_set.h:465:33:   required from ‘std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::emplace(_Args&& ...) [with _Args = {int&}; _Key = int; _Compare = cmp; _Alloc = std::allocator<int>; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree<int, int, std::_Identity<int>, cmp, std::allocator<int> >::const_iterator; typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other = std::allocator<int>; typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key> = __gnu_cxx::__alloc_traits<std::allocator<int>, int>::rebind<int>; typename _Alloc::value_type = int]’
answer.code:24:34:   required from here
/usr/include/c++/13/bits/stl_tree.h:772:15: error: static assertion failed: comparison object must be invocable as const
  772 |               is_invocable_v<const _Compare&, const _Key&, const _Key&>,
      |               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_tree.h:772:15: note: ‘std::is_invocable_v<const cmp&, const int&, const int&>’ evaluates to false