#include<bits/stdc++.h> using namespace std; int n,m,v[1001],w[1001],ans,dp[1001][1001]; void dfs(int i,int wi,int vi) { if(i>n) { if(vi>ans) { ans=vi; } return ; } if(wi+w[i]<=m && dp[i][wi+w[i]]<vi+v[i]) { dp[i][wi+w[i]]=vi+v[i]; dfs(i+1,wi+w[i],vi+v[i]); } if(dp[i][wi]<vi) { dp[i][wi]=vi; dfs(i+1,wi,vi); } } int main() { int t; cin>>t; while(t--) { cin>>m>>n; memset(dp,-1,sizeof(dp)); for(int i=1;i<=n;i++) { cin>>v[i]; } for(int i=1;i<=n;i++) { cin>>w[i]; } ans=0; dfs(1,0,0); } cout<<ans<<endl; return 0; }