Arpa와 수 목록

Arpa는 n개의 수가 들어 있는 목록을 발견했다. 그는 목록이 비어 있지 않고 목록에 있는 수들의 gcd(자세한 내용은 참고 절 참조)가 1일 때, 그리고 그럴 때에만 그 목록을 나쁜 목록이라고 부른다.

Arpa는 두 가지 연산을 수행할 수 있다:

• 수 하나를 선택해 비용 x를 지불하고 삭제한다.
• 수 하나를 선택해 비용 y를 지불하고 1만큼 증가시킨다.

Arpa는 원하는 만큼 많은 수에 이 연산들을 적용할 수 있으며, 같은 수에 두 번째 연산을 임의의 횟수만큼 적용하는 것도 허용된다.

Help Arpa 목록을 좋은 목록으로 만드는 데 필요한 가능한 최소 비용을 구한다.

첫째 줄에는 세 정수 n, x, y (1 ≤ n ≤ 5·105, 1 ≤ x, y ≤ 109) — 목록의 원소 수와 정수 x 및 y가 주어진다.

둘째 줄에는 n개의 정수 a1, a2, ..., an (1 ≤ ai ≤ 106) — 목록의 원소들이 주어진다.

목록을 좋은 목록으로 만드는 데 필요한 가능한 최소 비용을 나타내는 정수 하나를 출력한다.

예제에서는 수 1을 삭제해야 하고(비용 23), 수 16을 1만큼 증가시켜야 한다(비용 17).

수 집합의 gcd(최대공약수)는 그 집합의 모든 정수를 나누는 정수 중 최댓값이다. gcd에 관한 자세한 내용은 여기에서 확인할 수 있다.