#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; using ll = long long; using P = pair; constexpr int INF = 1001001001; constexpr int mod = 1000000007; // constexpr int mod = 998244353; template inline bool chmax(T& x, T y){ if(x < y){ x = y; return true; } return false; } template inline bool chmin(T& x, T y){ if(x > y){ x = y; return true; } return false; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, p; cin >> n >> m >> p; vector a(n), b(n), c(n, 1); int amax = 0, bmax = 0, cmax = 0; map mp; for(int i = 0; i < n; ++i){ cin >> a[i]; chmax(amax, a[i]); b[i] = a[i]; while(b[i] % p == 0){ b[i] /= p; c[i] += 1; } chmax(bmax, b[i]); chmax(cmax, c[i]); chmax(mp[c[i]], b[i]); } if(amax > m){ cout << 1 << endl; return 0; } if(bmax == 1){ cout << -1 << endl; return 0; } int MAX = cmax * cmax; vector powp(MAX, 1); for(int i = 1; i < MAX; ++i) powp[i] = powp[i - 1] * p; vector dp(MAX + 1); dp[0] = 1; int m2 = (m + amax - 1) / amax; int ans = INF; for(auto [cost, val] : mp){ if(val == 1) continue; for(int i = 0; i <= MAX - cost; ++i){ if(dp[i] == 0) continue; if(dp[i] * val * powp[max(0, cost - 1)] > m) chmin(ans, i + 1); chmax(dp[i + cost], min(m2, dp[i] * val)); } } for(int i = 0; i <= MAX; ++i){ if(dp[i] >= m2) chmin(ans, i + 1); } for(int i = 0; i < n; ++i){ if(b[i] == 1) continue; ll prod = 1; int sum = 0; while(prod <= m){ sum += 1; if(prod * amax > m){ prod *= amax; } else if(prod * a[i] > m){ prod *= a[i]; } else{ prod *= b[i]; sum += c[i]; } } chmin(ans, sum); } cout << ans << endl; return 0; }