#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<cstdlib>
#include<iomanip>
#include<queue>
#include<vector>
#include<bitset>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=505;
const int maxm=2e3+5;
const int inf=2e9;
inline int read()
{
	int x=0,y=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') y=-1; c=getchar();}
	while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x*y;
}
int n,m;
struct edge
{
	int to,next,c,w,u;
}g[maxm<<1];
int head[maxn],cnt(0);
inline void add(int a,int b,int c,int w)
{
	g[cnt].to=b; g[cnt].u=a;
	g[cnt].c=c; g[cnt].w=w;
	g[cnt].next=head[a];
	head[a]=cnt++;
	return ;
}
void Add(int a,int b,int c,int w)
{add(a,b,c,w); add(b,a,0,-w);}
int dis[maxn],vis[maxn];
int pre[maxn];
bool spfa(int s,int t)
{
	memset(dis,-1,sizeof(dis));
	memset(pre,-1,sizeof(pre));
	memset(vis,0,sizeof(vis));
	queue<int> q;
	q.push(s); dis[s]=0; vis[s]=1;
	while(!q.empty())
	{
		int u=q.front(); q.pop(); vis[u]=0;
		for(int i=head[u];i!=-1;i=g[i].next)
		{
			int v=g[i].to;
			if(!g[i].c) continue;
			if(dis[v]<dis[u]+g[i].w)
			{
				dis[v]=dis[u]+g[i].w;
				pre[v]=i;
				if(!vis[v]) q.push(v),vis[v]=1;
			}
		}
	}
	return (pre[t]!=-1);
}
pii EK(int s,int t)
{
	int ans(0),res=0;
	while(spfa(s,t))
	{
		int mn=2e9;
		for(int i=t;i!=s;i=g[pre[i]].u)
			mn=min(mn,g[pre[i]].c);
		for(int i=t;i!=s;i=g[pre[i]].u)
		{
			g[pre[i]].c-=mn;
			g[pre[i]^1].c+=mn;
			ans+=mn*g[pre[i]].w;
		}
		res+=mn;
	}
	return make_pair(res,ans);
}
int lim[maxn],tot(0);
int S,T;
int col[maxn],val[maxn];
int deg[maxn];
void solve()
{
	int sum=0;
	memset(head,-1,sizeof(head));
	memset(deg,0,sizeof(deg));
	tot=0; S=2*n+m+2; T=2*n+m+1;
	n=read(); m=read();
	for(int i=1;i<=m;i++)
	{
		lim[i]=read(); Add(S,i,inf,0);
		deg[i]+=lim[i];
	}
	for(int i=1;i<=n*2;i++)
	{
		col[i]=read(); val[i]=read();
		Add(col[i],m+i,1,val[i]);
	}
	for(int i=1;i<=n*2;i++)
	{
		int tmp=ceil(i*1.0/2);
		Add(m+i,m+i+1,n-tmp,0);
		deg[m+i]-=tmp; deg[m+i+1]+=tmp;
	}
	Add(T,S,inf,0);
	int ss=2*n+m+3,tt=2*n+m+4;
	for(int i=1;i<=n*2+m;i++)
	{
		if(deg[i]>0) Add(ss,i,deg[i],0),sum+=deg[i];
		else if(deg[i]<0) Add(i,tt,-deg[i],0);
	}
	pii tmp=EK(ss,tt);
	if(tmp.first!=sum) {printf("-1\n"); return ;}
	printf("%d\n",EK(S,T).second+tmp.second);
	return ;
}
int main()
{
	int T=read();
	while(T--) solve();
	return 0;
}