#include #include #include using namespace std; int main(){ int C, N; cin >> C >> N; vector a(N); for(int i = 0; i < N; i++){ cin >> a[i]; } for(int i = 1; i < a.size(); i++){ if(a[i] == a[i-1]){ a.erase(a.begin()+i); i--; } } N = a.size(); vector > dp(N+1, vector(C+1, 1000*1000*1000)); dp[0][0] = 0; for(int i = 0; i < N; i++){ for(int j = 0; j <= C; j++){ dp[i+1][j] = dp[i][j]; } for(int j = 0; j < a[i]; j++){ if(dp[i][j] == 1000*1000*1000) continue; int cost = dp[i][j]; for(int k = j; k <= C; k += a[i]){ dp[i+1][k] = min(dp[i+1][k], cost); cost = dp[i+1][k] + 1; //cerr << i << " : " << k << " : " << dp[i+1][k] << endl; } } } if(dp[N][C] == 1000*1000*1000){ cout << -1 << endl; }else{ cout << dp[N][C] << endl; } return 0; }