def factorize(n): factors = {} i = 2 while i * i <= n: while n % i == 0: factors[i] = factors.get(i, 0) + 1 n = n // i i += 1 if n > 1: factors[n] = 1 return factors def get_divisors(factors): divisors = [1] for p in factors: exponents = [p**e for e in range(1, factors[p] + 1)] new_divisors = [] for d in divisors: for e in exponents: new_divisors.append(d * e) divisors += new_divisors divisors = list(set(divisors)) divisors.sort() return divisors def main(): import sys from collections import defaultdict import heapq N, M, A, B = map(int, sys.stdin.readline().split()) C = list(map(int, sys.stdin.readline().split())) forbidden = set(C) if 1 in forbidden or N in forbidden: print(-1) return factors = factorize(N) divisors = get_divisors(factors) D = divisors adj = defaultdict(list) for d in D: if d == N: continue for m in D: if m > d and m % d == 0: f = m // d if f < 2: continue valid = True for c in forbidden: if c % d == 0: q = c // d if 1 <= q <= f: valid = False break if valid: cost = (f - 1) * A if m != N: cost += B adj[d].append((m, cost)) INF = float('inf') dist = {d: INF for d in D} dist[1] = 0 heap = [] heapq.heappush(heap, (0, 1)) visited = set() while heap: current_dist, u = heapq.heappop(heap) if u in visited: continue if u == N: print(current_dist) return visited.add(u) for v, cost in adj[u]: if dist[v] > current_dist + cost: dist[v] = current_dist + cost heapq.heappush(heap, (dist[v], v)) print(-1) if __name__ == "__main__": main()