연속 접속 보너스 장부

문제

한 게임 서버는 이용자의 일별 접속 기록을 읽어 출석 보상으로 지급한 토큰의 총개수를 계산한다. 기록은 날짜가 이른 순서로 주어지며, 각 날짜의 값은 접속했으면 1, 접속하지 않았으면 0이다. 서버는 기록에 등장하는 첫날 직전까지의 연속 접속 일수를 0으로 놓고 계산을 시작한다. 기록에 없는 과거의 접속이나 보상은 고려하지 않는다. 접속한 날에는 먼저 연속 접속 일수를 1 늘리고, 기본 보상으로 토큰 A개를 지급한다. 이렇게 늘어난 연속 접속 일수가 K의 배수이면 그날 토큰 B개를 추가로 지급한다. 추가 보상을 지급해도 연속 접속 일수는 초기화하지 않는다. 따라서 한 번도 빠지지 않고 2K일 동안 접속했다면 K번째 날과 2K번째 날에 각각 추가 보상을 받는다. 기본 보상과 추가 보상은 같은 날 함께 지급될 수 있다. 접속하지 않은 날에는 어떤 토큰도 지급하지 않고 연속 접속 일수를 즉시 0으로 바꾼다. 이후 다시 접속하면 새로운 연속 접속 기록의 첫날로 센다. 접속하지 않은 날이 여러 번 이어져도 연속 접속 일수는 계속 0이다. 토큰을 회수하거나 이전 날짜의 보상을 수정하는 규칙은 없다. 서버가 확인하려는 값은 마지막 날의 연속 접속 일수나 보상을 받은 날짜의 수가 아니라, 주어진 N일 동안 지급한 모든 토큰의 합이다. N, K, A, B와 접속 기록을 받아 이 합을 구한다. 모든 날짜에 접속하지 않았다면 지급한 토큰이 없으므로 0을 출력한다. 이용자 사이의 순위를 비교하는 작업은 없으므로 동점 처리도 필요하지 않다.

입력

첫째 줄에 정수 N, K, A, B가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000, 1 ≤ A ≤ 100, 0 ≤ B ≤ 1,000이다.
둘째 줄에 N개의 정수가 날짜가 이른 순서로 공백으로 구분되어 주어진다. 각 정수는 0 또는 1이다.

출력

N일 동안 지급한 토큰의 총개수를 정수 하나로 출력한다.

8 3 2 5
1 1 1 0 1 1 1 1

24

4 1 3 2
0 0 0 0

0

6 2 1 4
1 1 1 1 1 1

18

출처: Devin.KR 자체 제작