BBB

Byteasar는 Byteotian Bit Bank(줄여서 BBB)에 계좌를 하나 가지고 있습니다. 이 계좌는 처음에 $p$ bythaler로 시작해 마지막에 $q$ bythaler로 끝났습니다. 모든 거래는 정확히 1 bythaler를 입금하거나 출금하는 것이었고, 어느 순간에도 잔액이 음수가 된 적은 없습니다.

은행 창구 직원이 계좌 명세서를 출력했습니다. 명세서는 $n$개의 기호가 적힌 종이 띠이며, +는 1 bythaler 입금을, -는 1 bythaler 출금을 뜻합니다. 그런데 일부 기호가 잘못 입력된 것으로 밝혀졌습니다. 직원은 명세서를 다시 출력할 수 없고, 이미 인쇄된 명세서를 그 자리에서 고쳐야 합니다. 고친 명세서가 실제 거래와 똑같을 필요는 없고, 다음 두 조건만 만족하면 됩니다.

• 명세서의 거래 순서와 처음 잔액 $p$로부터 계산한 마지막 잔액이 $q$와 일치한다.
• 거래를 왼쪽에서 오른쪽으로 따라갈 때, 잔액이 한 번도 음수가 되지 않는다.

직원은 다음 두 가지 편집을 할 수 있습니다.

• 원하는 기호 하나를 반대 기호로 바꾼다(+를 -로, 또는 -를 +로). 한 번에 $x$초가 걸린다.
• 명세서의 맨 마지막 기호를 떼어 맨 앞으로 옮긴다. 한 번에 $y$초가 걸린다.

예를 들어 $p = 2$, $q = 3$일 때 명세서 --++-+-++-+-+는 이미 올바릅니다. 반면 ---++++++는 올바르지 않습니다. 세 번째 거래 후에 잔액이 음수가 되고, 마지막 잔액도 $3$이 아니라 $5$가 되기 때문입니다. 이 명세서는 끝에서 두 번째 기호를 반대로 바꾼 뒤 맨 마지막 기호를 맨 앞으로 옮기면 올바르게 만들 수 있습니다.

명세서를 올바르게, 즉 처음 잔액과 마지막 잔액이 일치하고 잔액이 한 번도 음수가 되지 않도록 고치는 데 필요한 최소 시간(초)을 구하세요.

첫째 줄에 다섯 정수 $n$, $p$, $q$, $x$, $y$가 공백 하나로 구분되어 주어집니다($1 \le n \le 10^6$, $0 \le p, q \le 10^6$, $1 \le x, y \le 10^3$). 각각 거래의 개수, 처음 잔액, 마지막 잔액, 기호 하나를 뒤집는 데 걸리는 시간(초), 맨 마지막 기호를 맨 앞으로 옮기는 데 걸리는 시간(초)을 뜻합니다. 둘째 줄에 + 또는 -로 이루어진 길이 $n$의 문자열이 공백 없이 주어집니다.

명세서를 올바르게 고치는 데 필요한 최소 시간(초)을 정수 하나로 출력하세요. 고칠 필요가 없으면 $0$을 출력합니다. 올바르게 고치는 방법은 항상 존재함이 보장됩니다.