Background

Shiota Nagisa (潮田 渚) is not very good at science subjects, so Koro-sensei (杀老师), who carefully observes students, would naturally notice. Therefore, Nagisa has to join the after-class final exam Slippery Slippery Tutoring Class held by Koro-sensei. As for why it has this name, well, you cannot ask me.

Problem Description

In the tutoring class, because multiple students may have needs at the same time, Koro-sensei will create clones and move back and forth at the speed of sound to answer questions.

There are $n$ students in the class, and each of them has one question. In order to answer students' questions in an orderly way, Koro-sensei lines up all students into a single row. The question of the $i$-th student has a difficulty value $a_i$, and answering the $i$-th student's question costs Koro-sensei $a_i$ energy. Wherever Koro-sensei goes, it must solve that student's question. Koro-sensei will start by solving the first student's question in the sequence, and it will finally go to solve the last student's question.

Each time after solving one student's question and moving to the next student's seat, Koro-sensei needs to spend $k$ energy. Specially, if Koro-sensei wants to make things easier, it can choose not to move to the next one, but jump directly to the second next, the third next, and so on, so it does not need to solve the questions of the skipped students. Correspondingly, it will be teased by the students. Feeling upset, Koro-sensei will naturally spend extra energy, and the energy cost is $k+(q-p-1) \times d$ (the current position is $p$, and it jumps to position $q$).

Of course, Koro-sensei also has speed, and it still wants to solve some students' questions. Therefore, Koro-sensei will skip at most $x-1$ students at a time, i.e. it will go on to solve the question of the next $x$-th student.

Input Format

The first line contains five integers $n,k,d,x,tp$, meaning there are $n$ students; moving only in order to the next student's seat costs $k$ energy; for each additional skipped student, it costs an extra $d$ energy; each move can skip at most $x-1$ students; and whether this is special testdata.

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

• If $tp=1$, the second line contains one integer $Seed$ as the seed, and then call the $rnd$ function to generate $n$ integers in order as the array $a$, where $a_i$ is 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

One line with one integer, meaning the minimum total energy Koro-sensei needs to spend to finish solving the last student's question.

5 3 4 1 0
1 2 3 4 5

27

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

717318

10000000 899999999 923456655 213111 1
1314520

9231813656566921

Hint

Sample Explanation #1

Koro-sensei cannot skip students each time, so it must move in order and solve all questions. Therefore, the answer is the energy needed to solve the questions $1+2+3+4+5=15$ plus the energy needed for moving $4 \times 3=12$, so the total energy cost is $27$.

Constraints

This problem uses bundled testdata.

• Subtask 1 (20 points): the students study seriously and behave well, so fewer students will remain: $tp=0$, $n \leq 10^3$.
• Subtask 2 (30 points): Koro-sensei is extremely fast, and the students have no 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 testdata, $1 \leq n \leq 10^7$, $0 \leq k,d,a_i \leq 10^9$, $1 \leq x \leq n-1$.

Hint

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

Translated by ChatGPT 5