시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 19 6 5 41.667%

문제

N개의 정수로 이루어진 배열 ai가 주어져 있다. 이 배열에 다음과 같은 두 종류의 연산을 수행하려고 한다.

  1. 배열에서 길이 m인 연속한 구간을 삭제한다.
  2. 배열의 있는 수 ai에 1을 더하거나 뺀다.

1번 연산은 최대 1번만 수행할 수 있고, 2번 연산은 각 수에 대해 최대 1번만 수행할 수 있다.

1번 연산의 비용은 m×A, 2번 연산의 비용은 1번에 B이다. 주어진 배열의 GCD를 1보다 크게 만드려고 할 때 필요한 최소 비용을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, A, B가 주어진다. (1 ≤ N ≤ 1,000,000; 1 ≤ A, B ≤ 109)

둘째 줄에는 배열에 들어있는 수 a1, a2, ..., aN이 주어진다. (2 ≤ ai ≤ 109)

출력

첫째 줄에 배열의 GCD를 1보다 크게 만드는 최소 비용을 출력한다.

예제 입력 1

3 1 4
4 2 3

예제 출력 1

1

예제 입력 2

5 3 2
5 17 13 5 6

예제 출력 2

8

예제 입력 3

8 3 4
3 7 5 4 3 12 9 4

예제 출력 3

13

힌트

예제 1은 1번 연산으로 3번째 수를 삭제하면 최소 비용이다.

예제 2는 1번 연산으로 2~3번째 수를 삭제, 2번 연산으로 5번째 수를 1 줄이면 최소 비용이다.

출처

  • 문제의 오타를 찾은 사람: jh05013