24028번 - 사진 촬영

곧 졸업을 앞두고 있는 준혁이는 친구들과 기념사진을 찍어 추억을 남기려고 한다. 그러나 준혁이와 친구들이 방문한 사진관은 다음과 같은 특별한 조건들을 요구했다.

$N$명의 친구들이 일렬로 줄을 서서 사진을 여러 장 찍으며, 모든 친구들이 적어도 한 장의 사진에 최소 한번씩 등장하게 사진을 촬영하고자 한다. 사진을 촬영하는 방법은 다음과 같다.

1. 한 사람의 독사진을 촬영한다. 이 때 드는 비용은 그 사람의 고유한 비용 $A_i$원이다.
2. 원하는 위치의 인접한 두 사람의 위치를 바꾼다. 이 때 드는 비용은 $C$원이다.
3. 연속한 구간에 놓여 있는 친구들의 단체 사진을 촬영한다. 이 때 드는 비용은 사진에 찍히는 한 사람당 $B$원으로, 전체 비용은 $B \times ($구간 길이$)$ 이다. 단, 기술적인 문제로 단체 사진에는 $K$명 이상의 친구들이 나와야만 촬영할 수 있다.

현재 친구들은 이미 일렬로 서서 사진 촬영만을 기다리고 있다. 준혁이를 도와 모든 친구들이 적어도 한 장의 사진에 최소 한번씩 등장하도록 사진을 찍을 때의 최소 비용을 구하도록 하자.

첫 번째 줄에 $N$, $K$, $B$, $C$가 공백으로 구분되어 주어진다. ($1 \leq N \leq 5,000$, $1 \leq K \leq N$, $0 \leq B \leq 10^9$, $0 \leq C \leq 10^9$)

다음 줄에 $N$개의 정수 $A_i$이 주어진다. ($0 \leq A_i \leq 10^9$)

첫 번째 줄에 모든 친구들이 적어도 한 장의 사진에 최소 한번씩 등장하도록 사진을 찍을 때의 최소 비용을 출력한다.