Killer Teacher's Cloned Movement

In a tutoring center, there are n students lined up, each with one question. The difficulty of the question for the i-th student is given by a_i, and solving it costs a_i energy. Killer Teacher starts by answering the first student's question and must eventually answer the last student's question.

Moving from one student at position p to another at position q incurs a moving cost. If moving to the next student (i.e. when q-p=1), the cost is k. However, the teacher is allowed to skip some students. If the teacher jumps from position p to q (where q-p≥2), the cost is

Note that in any jump the teacher can skip at most x-1 students, which means the jump length (q-p) cannot exceed x.

The task is to choose which students' questions to answer (always including the first and the last) and determine the sequence of moves so that the total energy cost (solving questions plus moving) is minimized.

Input Format: The first line contains four integers: n, k, d, and x. The second line contains n integers representing the array a, i.e. the energy costs for answering each student's question.

Output Format: Output a single integer representing the minimum energy required.

inputFormat

The input is read from standard input. The first line contains four integers: n (1 ≤ n ≤ 10⁵), k, d, and x (x ≥ 1), where:

• n is the number of students.
• k is the base cost of moving from one student to an adjacent one.
• d is the additional cost per student skipped.
• x indicates that the teacher can jump up to x positions (i.e. skip at most x-1 students).

The second line contains n integers a₁, a₂, ..., a_n where a_i is the energy cost to solve the i-th student's question.

outputFormat

Output a single integer which is the minimum energy required for the teacher to answer the first and last student's questions while satisfying the movement constraints.

sample

5 3 2 2
1 2 3 4 5

19