#include <bits/stdc++.h>

typedef int in;

#define int long long

using namespace std;

int dp[1000001];

int minCoin(int v,int n ,int * arr){

```
if(v==0){
return dp[v]=0;
}
if(dp[v]!=-1){
return dp[v];
}
int ans=INT_MAX;
int count =0;
for(int i=0;i<n;i++){
if(v>=arr[i]){
int subprob = minCoin(v-arr[i],n,arr)+1;
ans = min(ans,subprob);
}
else{
count++;
}
}
if(count==n){
return dp[v]=-1;
}
else
return dp[v]=ans;
```

}

in main() {

//code

int t;

cin>>t;

while(t–){

memset(dp,-1,sizeof(dp));

int n,v;

cin>>v>>n;

int *arr= new int[n];

for(int i=0;i<n;i++){

int x;

cin>>arr[i];

//arr.push_back(x);

}

```
cout<<minCoin(v,n,arr)<<endl;
}
return 0;
```

}