갈까마귀와 까마귀

닉은 새를 관찰하는 사람이다. 같은 취미를 가진 사람들과 이야기하려고 포럼 "CrowFinders"에 자주 들어간다. 이 포럼에는 투표 기능이 있어서 사용자가 댓글에 추천 또는 비추천을 할 수 있다. 투표 한 번마다 댓글의 점수가 1씩 오르거나 내려가므로, 댓글 점수는 음수를 포함한 어떤 정수든 될 수 있다.

어느 날 닉은 갈까마귀가 까마귀인지를 두고 뜨겁게 벌어진 토론을 발견했다. 그 토론에서 점수가 양수와 음수를 번갈아 가지는 댓글 묶음을 보았다. 며칠 뒤 이 댓글 묶음은 더 이상 번갈아 가지 않았다. 닉은 댓글 묶음을 다시 번갈아 가도록 만들고 싶어 한다.

댓글 묶음의 점수 $s_1, s_2, \ldots, s_n$이 모두 0이 아니고, 인접한 점수 $s_i, s_{i+1}$의 부호가 늘 반대이면 그 묶음은 번갈아 간다. 0이 아닌 점수의 댓글이 하나뿐인 묶음이나 댓글이 하나도 없는 묶음도 번갈아 가는 묶음이다.

닉이 쓸 수 있는 연산은 두 가지다. 첫째, 가짜 계정을 만들어 그 계정으로 댓글 일부에 추천 또는 비추천을 하는 것이다. 선택한 댓글의 점수는 1씩 바뀐다. 각 가짜 계정은 같은 댓글에 최대 한 번만 투표할 수 있고, 댓글의 임의의 부분집합에 투표할 수 있다. 계정을 만들어 투표하는 데는 투표하는 댓글이 몇 개이든 $c$초가 걸린다. 둘째, 특정 댓글을 신고해서 묶음에서 제거하는 것이다. 신고 사유를 설득력 있게 생각해 내는 데 $r$초가 걸린다. 신고는 항상 성공하므로 댓글은 반드시 제거된다.

닉은 이 연산들을 어떤 순서로든, 몇 번이든 적용할 수 있다. 댓글 묶음이 번갈아 가도록 만드는 데 필요한 최소 시간을 구하라.

첫째 줄에 세 정수 $n$, $c$, $r$ ($1 \le n \le 5 \cdot 10^5$, $1 \le c, r \le 10^9$)이 주어진다. 각각 댓글의 개수, 가짜 계정을 만드는 데 걸리는 시간, 댓글 하나를 신고하는 데 걸리는 시간이다. 둘째 줄에는 $n$개의 정수 $s_1, \ldots, s_n$ ($-10^9 \le s_i \le 10^9$이 모든 $i$에 대해 성립)이 주어진다. 각 댓글의 현재 점수다.

댓글 묶음을 번갈아 가도록 만드는 데 필요한 최소 시간을 출력하라.