警示后人！

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 10002;
int n,m;
int a[N],b[N];
bool vis[N*2];
int dist[N*2];
int d[N*2],f[N*2];
priority_queue<pair<int,int> >q;//大根堆 

void solve(){
	cin>>n>>m;
	for(int i = 1;i <= m;i++) cin>>a[i];
	for(int i = 1;i <= m;i++) cin>>b[i];

	memset(vis,0,sizeof vis);
	memset(d,0x3f,sizeof d);
	d[N] = 0;
	q.push({0,N});
	while(!q.empty()){
		long long now = q.top().second;
		q.pop();
		if(vis[now] == 1) continue;
		vis[now] = 1;
		
		for(int i = 1;i <= m;i++){
			long long to1 = now + a[i];
			long long to2 = now - a[i];
			
			if(d[to1] > d[now] + b[i] && to1 <= 20000 && vis[to1] == 0){
				d[to1] = d[now] + b[i];
				q.push({-1*d[to1] , to1});
			}
			if(d[to2] > d[now] + b[i] && to2 >= 0 && vis[to2] == 0){
				d[to2] = d[now] + b[i];
				q.push({-1*d[to2] , to2});
			}
		} 
	}
	
	for(int i = 0;i <= N;i++)
		dist[i] = d[N+i];
			
	memset(f,0x3f,sizeof f);
	f[0] = f[1] = 0;
	for(int i = 2;i <= n;i++)
		for(int j = 1;j < i;j++)
			f[i] = min(f[i] , max(f[i-j]+ dist[j] , f[j] + dist[j]));
	
	if(f[n] >= 0x3f3f3f3f) cout<<"-1"<<"\n";
	else cout<<f[n]<<"\n";
	return;
}

signed main()
{
	
	//freopen("guess5.in","r",stdin);
//	freopen("1.out","w",stdout);
	int c,T;
	cin>>c>>T;
	while(T--){
		solve();		
	}
	return 0;
}