#7 WA 求调

#include<bits/stdc++.h>
using namespace std;
#define N 10005
#define M 1005
#define int long long
int n,m,i,j,ans,t,c,a[M],b[M],f[N<<1],dp[N];
signed main(){
	scanf("%lld%lld",&c,&t);
	while(t--){
		scanf("%lld%lld",&n,&m);
		for(i=1;i<=m;i++) scanf("%lld",&a[i]);
		for(i=1;i<=m;i++) scanf("%lld",&b[i]);
		memset(f,63,sizeof(f));
		f[n]=0;
		for(i=1;i<=m;i++){
			for(j=-n+a[i];j<=n;j++) f[j+n]=min(f[j+n],f[j-a[i]+n]+b[i]);
			for(j=n-a[i];j>=-n;j--) f[j+n]=min(f[j+n],f[j+a[i]+n]+b[i]);
		}
		memset(dp,63,sizeof(dp));
		dp[1]=0;
		for(i=2;i<=n;i++){
			for(j=1;j<i;j++) dp[i]=min(dp[i],max(dp[j],dp[i-j])+f[j+n]);
		}
		if(dp[n]>=1e18) puts("-1");
		else printf("%lld\n",dp[n]);
	}
	return 0;
}