라면 사기 (Large)
시간 제한1초메모리 제한64 MB
공장 i에서 A[i]개의 라면을 사야 하며, 한 개, 인접한 두 개, 인접한 세 개 묶음 거래로 최소 비용을 구한다.
문제
라면을 좋아하는 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장에는 1번부터 N번까지 차례대로 번호가 붙어 있다. 교준이는 i번 공장에서 정확히 Ai개의 라면을 사려고 한다(1 ≤ i ≤ N).
교준이가 라면을 살 수 있는 방법은 다음 세 가지다.
- i번 공장에서 라면을 하나 산다(1 ≤ i ≤ N). 이때 비용은 B원이다.
- i번 공장과 (i+1)번 공장에서 라면을 하나씩 산다(1 ≤ i ≤ N-1). 이때 비용은 (B+C)원이다.
- i번 공장과 (i+1)번 공장, (i+2)번 공장에서 라면을 하나씩 산다(1 ≤ i ≤ N-2). 이때 비용은 (B+2C)원이다.
최소 비용으로 라면을 사려고 할 때 교준이에게 필요한 금액을 출력하는 프로그램을 작성하시오.
입력
첫 번째 줄에 라면 공장의 개수 N과 두 자연수 B, C가 공백을 사이에 두고 주어진다.
두 번째 줄에 N개의 정수 A1, ..., AN가 공백을 사이에 두고 주어진다.
출력
첫 번째 줄에 교준이에게 필요한 최소 금액을 출력한다.
제한
모든 입력 데이터는 다음 조건을 만족한다.
- 3 ≤ N ≤ 106
- 1 ≤ B ≤ 106
- 1 ≤ C ≤ 106
- 0 ≤ Ai ≤ 106 (1 ≤ i ≤ N)