#include<bits/stdc++.h> #include<algorithm> #include<bitset> #include<cctype> #include<cerrno> #include<clocale> #include<cmath> #include<complex> #include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> #include<deque> #include<exception> #include<fstream> #include<functional> #include<limits> #include<list> #include<map> #include<iomanip> #include<ios> #include<iosfwd> #include<iostream> #include<istream> #include<ostream> #include<queue> #include<set> #include<sstream> #include<stack> #include<stdexcept> #include<streambuf> #include<string> #include<utility> #include<vector> #include<cwchar> #include<cwctype> using namespace std; #define int long long const int N = 1e6 + 10; const int INF = 0x3f3f3f3f; int n, m, x, y; int a[10], len, f[N], num[N]; void dfs(int k, int now){ if(now > n) return ; if(k == m + 1){ if(now != 1) num[++len] = now; return ; } int cnt = 1; while(now * cnt <= n){ dfs(k + 1, now * cnt); cnt *= a[k]; } } signed main() { for(int i = 0;i <= 5000; i++){ f[i] = 1e9; } cin >> n >> m >> x >> y; if(x > y) return printf("-1"), 0; for(int i = 1;i <= m;i++){ cin >> a[i]; } sort(a + 1,a + 1 + m); m = unique(a + 1,a + 1 + m) - a - 1; dfs(1, 1); sort(num + 1, num + 1 + len); for(int i = 1;i <= len; i++){ f[num[i]] = 1; } for(int i = num[1];i <= n;i++){ for(int j = 1;j <= len && num[j] <= i;j++) f[i] = min(f[i], f[i - num[j]] + 1); } printf("%d\n",(f[n] == 1e9 ? -1 : f[n])); return 0; }

😄 😄 😄 😄 😄 😄 😄 😄 😄 😄 😄 😄 😄 😄 😄 😄 😄 😄 😄 😄 😄 😄 😄 😄 😄 😄