관측 기록의 보정 묶음

문제

한 날씨 관측소는 N일 동안 수집한 관측 기록을 보관하고 있다. 각 날짜의 기록에는 그날 센서가 흔들린 정도를 나타내는 정수 등급 A_i가 붙어 있다. 등급은 보정 작업의 비용을 계산할 때만 사용하며, 보정 작업을 수행해도 원래 등급은 바뀌지 않는다. 관측소는 모든 날짜의 기록을 보정한 뒤 하나의 자료로 공개하려고 한다. 보정 장치는 두 가지 방식으로 실행할 수 있다. 첫 번째 방식은 하루의 기록만 보정하는 단일 작업이다. 어느 날짜를 선택하더라도 단일 작업의 비용은 C이다. 두 번째 방식은 날짜가 연속한 이틀의 기록을 한꺼번에 보정하는 연결 작업이다. i일과 i+1일을 연결 작업으로 보정하면 비용은 B+|A_i-A_{i+1}|이다. 여기서 두 등급의 차이는 큰 값에서 작은 값을 뺀 값이다. 모든 날짜는 정확히 하나의 작업에 포함되어야 한다. 어떤 날짜를 단일 작업으로 보정했다면 그 날짜를 연결 작업에 다시 포함할 수 없다. 서로 다른 연결 작업도 날짜를 공유할 수 없다. 하루를 건너뛴 두 날짜를 연결하거나, 사흘 이상의 기록을 한 번의 작업으로 처리하는 것은 허용하지 않는다. 첫날과 마지막 날은 서로 연속한 날짜로 취급하지 않는다. 작업을 실제로 실행하는 순서는 총비용에 영향을 주지 않는다. 각 작업의 비용은 그 작업에 포함된 날짜와 입력으로 주어진 값만으로 결정되며, 전체 비용은 선택한 모든 작업 비용의 합이다. 연결 작업의 비용이 두 번의 단일 작업 비용보다 크더라도 연결 작업 자체가 금지되는 것은 아니다. 반대로 연결 작업이 저렴하더라도 다른 날짜와의 조합까지 고려해야 한다. 관측소가 모든 날짜의 기록을 빠짐없이 보정하는 데 필요한 최소 총비용을 구해야 한다. 최소 비용을 만드는 방법이 여러 개이면 그 비용만 출력한다. 모든 날짜에 단일 작업을 적용할 수 있으므로 가능한 방법은 항상 존재한다.

입력

첫째 줄에 날짜 수 N, 단일 작업 비용 C, 연결 작업의 기본 비용 B가 공백으로 구분되어 주어진다. 둘째 줄에 날짜순으로 N개의 등급 A_1, A_2, …, A_N이 주어진다. 모든 입력값은 정수이며, 1≤N≤190,000, 1≤C≤1,000,000,000, 1≤B≤1,000,000,000, 0≤A_i≤9이다.

출력

모든 날짜를 정확히 한 번씩 보정하는 최소 총비용을 한 줄에 정수로 출력한다.

5 7 5
1 2 8 8 3

18

4 3 10
0 9 0 9

12

1 4 1
9

4

출처: Devin.KR 자체 제작