Problem Background

Shiota Nagisa, due to his poor performance in science, is noticed by his teacher, the assassin-sensei. Consequently, Nagisa has to join the assassin-sensei's post-class final exam sliding sliding tutoring class. The reason behind the name? Well, you can't ask me about that.

Problem Description

In the tutoring class, since multiple students may have questions simultaneously, the assassin-sensei creates clones to move at sonic speed to answer questions.

There are $n$ students in the class, each with a question. To answer the students' questions in an orderly manner, the assassin-sensei arranges all the students in a queue. The $i$-th student's question has a difficulty value $a_i$, and answering the $i$-th student's question requires $a_i$ energy. The assassin-sensei, starting from the first student in the sequence, will eventually move to the last student.

Each time the assassin-sensei finishes answering a student's question and moves to the next student's seat, it costs $k$ energy points. Specifically, if the assassin-sensei wants to take it easy, it can skip the next student and move to the second, third, and so on, without answering the skipped students' questions. Correspondingly, it will be teased by the students, which costs extra energy, calculated as $k + (q - p - 1) \times d$ (current position is $p$, jump to position $q$).

Of course, the assassin-sensei has its speed limits and wants to answer some questions, so it can skip at most $x-1$ students to answer the next $x$ students' questions.

Input Format

The first line contains five integers $n, k, d, x, tp$, representing $n$ students, the energy cost $k$ to move to the next student's seat, the additional energy cost $d$ for each student skipped, the maximum number of students $x-1$ it can skip, and whether it is a special dataset.

• If $tp=0$, the second line contains $n$ integers $a_{1 \dots n}$, where $a_i$ represents the difficulty value of the $i$-th student's question.

• If $tp=1$, the second line contains an integer $Seed$, used as a seed to generate $n$ integers sequentially for the array $a$ using the $rnd$ function, where $a_i$ represents the difficulty value of the $i$-th student's question.

inline int rnd () {
    static const int MOD = 1e9;
    return Seed = ( 1LL * Seed * 0x66CCFF % MOD + 20120712 ) % MOD;
}

Output Format

A single line containing an integer, representing the minimum energy the assassin-sensei needs to spend to finish answering the last student's question.

Sample Input and Output

Sample Input #1

5 3 4 1 0
1 2 3 4 5

Sample Output #1

27

Sample Input #2

10 30630 56910 2 0
7484 99194 86969 17540 29184 68691 91892 81564 93999 74280

Sample Output #2

717318

Sample Input #3

10000000 899999999 923456655 213111 1
1314520

Sample Output #3

9231813656566921

Notes/Hints

Sample Explanation #1

The assassin-sensei cannot skip any students, so it must move sequentially and answer all questions. The total energy cost is the sum of the energy needed to answer the questions $1+2+3+4+5=15$ and the energy needed for movement $4 \times 3=12$, resulting in a total of $27$.

Data Range

This problem uses subtask testing.

• Subtask 1 (20 points): Students are diligent and fewer remain: $tp=0$, $n \leq 10^3$.
• Subtask 2 (30 points): The assassin-sensei is extremely fast, and students don't have time to tease it: $tp=0$, $n \leq 10^6$.
• Subtask 3 (50 points): $tp=1$, with no other special constraints.

For $100\%$ of the data, $1 \leq n \leq 10^7$, $0 \leq k, d, a_i \leq 10^9$, $1 \leq x \leq n-1$.

Hint

For datasets where $tp=1$, the $rnd$ function is used only to reduce input size, and the standard algorithm does not depend on this data generation method.

见题面 Input 部分

见题面 Output 部分