#include<bits/stdc++.h> #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include 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; }

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