사내 지원 창구의 이틀 계약

문제

어느 회사의 IT 지원 담당자는 앞으로 N일 동안 외부 지원 인력이 필요한 날짜를 정리했다. 날짜는 1일부터 N일까지이며, 각 날짜에는 지원이 필요하거나 필요하지 않다는 정보만 기록되어 있다. 지원이 필요한 날짜에는 적어도 하나의 계약으로 그날을 담당하게 해야 한다. 지원이 필요하지 않은 날짜를 계약에 포함하는 것도 허용되지만, 그 사실만으로 별도의 할인이나 환급을 받지는 않는다. 지원 인력을 부르는 계약은 두 종류이다. 하루 계약은 날짜 하나를 지정하며 비용은 A이다. 이틀 계약은 연속한 두 날짜를 지정하며 비용은 B이다. 계약 비용은 지원이 필요한 날짜의 수와 관계없이 정해진 금액을 그대로 지불한다. 이틀 계약으로 서로 떨어진 두 날짜를 지정할 수 없으며, 1일 이전이나 N일 이후를 계약 기간에 포함할 수도 없다. 특히 N이 1이면 이틀 계약은 사용할 수 없다. 담당자는 계약을 여러 개 체결할 수 있지만, 서로 다른 계약의 담당 날짜가 겹쳐서는 안 된다. 예를 들어 2일과 3일을 담당하는 이틀 계약을 사용했다면 2일 또는 3일을 포함하는 다른 계약은 사용할 수 없다. 계약하지 않은 날짜가 중간에 있어도 되며, 지원이 필요하지 않은 날짜는 아무 계약 없이 남겨 두어도 된다. 지원이 필요한 날짜를 계약 없이 남기는 것은 허용되지 않는다. 회사는 모든 필수 날짜를 담당하면서 계약 비용의 합을 최소화하려고 한다. 하루 계약을 각 필수 날짜에 하나씩 사용하면 항상 조건을 만족하므로 불가능한 입력은 없다. 최소 비용을 만드는 계약 구성이 여러 가지여도 구성 자체를 출력하지 않는다. 지원이 필요한 날짜가 전혀 없으면 계약을 체결하지 않을 수 있으며, 이때 최소 비용은 0이다. 일정과 두 계약의 비용이 주어졌을 때 지불할 최소 총비용을 구한다.

입력

첫째 줄에 N, A, B가 공백으로 구분되어 주어진다. 둘째 줄에 길이가 N인 문자열 S가 주어진다. S의 i번째 문자가 1이면 i일에 지원이 필요하고, 0이면 필요하지 않다. N, A, B는 정수이며 1≤N≤200,000, 1≤A,B≤1,000,000,000이다. S는 문자 0과 1로만 이루어진다.

출력

모든 지원 필요 날짜를 담당하기 위한 최소 총비용을 정수 하나로 출력한다. 지원이 필요한 날짜가 없으면 0을 출력한다.

5 6 9
11011

18

3 8 3
101

11

1 7 2
0

0

출처: Devin.KR 자체 제작