Woburn Challenge 2016-17 Round 3 - Junior Division

You've been hooked on the latest game in the Pokémon series, Pokémon Navy Green, and have finally reached the final challenge! In the original game, this challenge would've been the Elite $4$, a series of $4$ dangerous Pokémon trainers to defeat in a row. By now, it's been generalized to be the Elite $N$ $(1\le N\le {10}^9)$. Its $N$ members are numbered from $1$ to $N$ in the order in which they must be defeated.

You've brought just two Pokémon with you to get the job done, Aeroxis and Brinoble – you've trained both to be incredibly powerful, so they're all you'll need. You initially have Aeroxis as your active Pokémon, with Brinoble stored away in a backup Pokéball. Before each of the $N$ battles (including the first one), you may choose to swap your Pokémon, changing which of the two is active. Doing so takes $S$ $(1\le S\le {10}^9)$ seconds. You'll then use your currently active Pokémon to battle against the next of the $N$ trainers. It takes Aeroxis $A$ $(1\le A\le {10}^9)$ seconds to defeat a trainer, and it takes Brinoble $B$ $(1\le B\le {10}^9)$ seconds to do the same. Note that you may not swap Pokémon during a battle.

Some members of the Elite $N$ will be using different types of Pokémon, however. In particular, $M$ $(1\le M\le 1000)$ of the trainers will be using cloud-type Pokémon, which Brinoble is extremely weak against – as such, you absolutely must use Aeroxis to battle each of them. The $i$-th of these $M$ cloud-type Pokémon trainers is trainer number $T_i$ of the Elite $N$. The numbers $T_{1\dots M}$ are distinct, and are given in increasing order $(1\le T_1<T_2<\cdots <T_M\le N)$.

Given that you optimally choose when to swap Pokémon, what's the minimum total amount of time required to defeat all $N$ members of the Elite $N$ in order?

In test cases worth $15/20$ of the points, $N\le {10}^5$.

Input Specification

The first line of input consists of five space-separated integers $N$, $M$, $A$, $B$, and $S$.
$M$ lines follow, with the $i$-th of these lines consisting of a single integer, $T_i$ (for $i=1\dots M$).

Output Specification

Output a single line consisting of a single integer – the minimum total amount of time required to defeat the Elite $N$, in seconds.
Note that the answer may not necessarily fit within a $32$-bit signed integer (you may need the long long type in C++, or long in Java).

Sample Input

20 5 5 2 5
5
6
11
17
19

Sample Output

91

Sample Explanation

One optimal strategy is as follows:

• Swap to Brinboble before the $1$st battle ($5$ seconds).
• Use Brinboble for battles $1\dots 4$ ($8$ seconds).
• Swap to Aeroxis ($5$ seconds).
• Use Aeroxis for battles $5\dots 6$ ($10$ seconds).
• Swap to Brinboble ($5$ seconds).
• Use Brinboble for battles $7\dots 10$ ($8$ seconds).
• Swap to Aeroxis ($5$ seconds).
• Use Aeroxis for battle $11$ ($5$ seconds).
• Swap to Brinboble ($5$ seconds).
• Use Brinboble for battles $12\dots 16$ ($10$ seconds).
• Swap to Aeroxis ($5$ seconds).
• Use Aeroxis for battles $17\dots 20$ ($20$ seconds).