fn costmap(val: usize, p: usize) -> (usize, usize) { let mut cnt = 1usize; let mut val = val; while val % p == 0 { cnt += 1; val /= p; } (val, cnt) } fn main() { let mut nmp = String::new(); std::io::stdin().read_line(&mut nmp).ok(); let nmp: Vec = nmp.trim().split_whitespace().map(|s| s.parse().unwrap()).collect(); let n = nmp[0]; let m = nmp[1]; let p = nmp[2]; let mut a = String::new(); std::io::stdin().read_line(&mut a).ok(); let a: Vec = a.trim().split_whitespace().map(|s| s.parse().unwrap()).collect(); let m = m+1; let maxval = *a.iter().max().unwrap(); if maxval >= m { println!("1"); return; } let paths = a.iter().map(|&v| costmap(v, p)).filter(|&v| v.0 > 1).collect::>(); if paths.is_empty() { println!("-1"); return; } let mut cnt2val = vec![0usize; 31]; for &(val, cnt) in paths.iter() { cnt2val[cnt] = cnt2val[cnt].max(val); } let mut dp = vec![vec![0usize; 1000]; 31]; dp[0][1] = maxval; for cnt in 1..31 { for j in 0..1000 { dp[cnt][j] = dp[cnt][j].max(dp[cnt-1][j]).min(m); if j >= cnt { dp[cnt][j] = dp[cnt][j].max(dp[cnt][j-cnt] * cnt2val[cnt]).min(m); } } } println!("{}", (0..1000).filter(|&i| dp[30][i] == m).nth(0).unwrap()); }