The Aurora is an aircraft-carrying aviation submersible.
The Aurora.
~N~ soldiers in para-mails (you can think of these as aircraft) are being deployed to one of 
~M~ stations on the main continent. To travel to their respective stations, soldiers may either fly there directly with their para-mail or hitch a ride on the Aurora, which will make one journey from station 
~1~ to station 
~2~ to station 
~3~ … all the way to station ~M~. Coincidentally, this is the only route to travel between stations; that is, if a soldier wanted to travel via their own para-mail instead, they would also have to take the same route as the Aurora (because flying too far from the main route is unsafe). For each station 
~i~ from ~1~ to 
~M-1~, it takes exactly 
~B~ seconds to travel to station 
~i+1~ via para-mail or 
~A~ seconds via the Aurora 
~(A < B)~. Whenever one or more soldiers reach their station and are flying via the Aurora, the Aurora must make a stop to let all soldiers who are deployed at that station get off. The total time the Aurora stops is 
~C \times x~, where 
~x~ is the number of soldiers that get off at that station. The soldiers get off one by one, so if three soldiers get off, the first soldier waits for 
~0~ seconds, the second soldier waits for 
~C~ seconds, and the last soldier waits for 
~C \times 2~ seconds. All soldiers and the Aurora will start at station ~1~.
The battle is beginning soon, and it is vital that each soldier arrives at their station as fast as possible. What is the minimum total time for all the soldiers to arrive at their stations?
Input Specification
The first line of input will contain ~N~ and ~M~, separated by a single space.
The second line of input will contain ~A~, ~B~, and ~C~, separated from each other by single spaces.
The third line of input will contain ~N~ integers, the assigned stations of each of the ~N~ soldiers. They will be integers from ~1~ to ~M~. At least one soldier will be deployed to station ~M~.
Constraints
For all subtasks:
~1 \le A, B, C \le 10^5~
~A < B~
Subtask 1 [30%]
~1 \le N, M \le 1\,000~
Subtask 2 [70%]
~1 \le N, M \le 10^5~
Output Specification
The first and only line of output should contain the minimum total time for all the soldiers to arrive at their stations.
Sample Input 1
5 6
1 2 1
4 5 3 6 2
Sample Output 1
21
Explanation of Output for Sample Input 1
Soldier 3 and 5 should fly directly to their stations. The rest of the soldiers should use the Aurora. The total time is 
~3+5+4+7+2 = 21~.
Sample Input 2
10 4
1 100000 1
4 3 4 2 3 2 4 3 1 4
Sample Output 2
56
Comments
If only one soldier gets off at say, station 1, will that cause another soldier going to station 2 to have to wait another C seconds (assuming they both take the Aurora)?
EDIT: I'm stupid. The Aurora will stop for x*c seconds for x soldiers
Can someone please explain sample input 2 for me, I dont see how 56 is obtained
Lets say a soldier 1 gets off before soldier 2. Will soldier 1's get-off Aurora time affect soldier 2's time?
Assuming they both take the Aurora, yes.
If soldiers 3 and 5 go to their stations, (22 = 4 minutes for soldier 3, and 12 = 2 minutes for soldier 5), where does the other numbers come from?
The other soldiers board the Aurora. Their time is calculated as described in the problem statement.
Why let the two soldiers go by themselves? Isn't it better just to take all the soldiers on the aurora? To get from 1 to 6, it is 5 minutes, and then each soldiers leaves, so 5 minutes. This would be 10 minutes no?
The waiting time of soldiers increases if other soldiers get off before them.
If soldiers 1-4 took the aurora, then why does soldier 3 take more time than soldier 1 if she is getting off at station 3 compared to 4?
Sorry, soldiers 3 and 5 (in input order) should be the ones flying.
Oh, that makes sense. I just spent a long time trying to figure that out. I guess that's what I get for not refreshing the page...
Is there some restriction on when/how the soldiers can fly themselves in? Reading the problem, I thought that the soldiers could all para-mail in in tandem (and independent of the Aurora), but that definitely doesn't make sense in the context of the sample input.
Your thought is correct (as far as I understand it). Which part of the sample input is unclear? I'll try to explain it.
EDIT: The explanation has been updated. I change the sample a bit, but forgot to change the explanation. Sorry!
I'm still in the dark a little, sorry...
If all the soldiers can just para-mail in without regard to each other or the Aurora, could they not all reach their stations within 10 units (in sample input 1)? Since B = 2, M = 6.
I'm probably just misreading badly. :)
If all soldiers use their para-mails, the total time will be
Note that you are asked to minimize the sum of the times instead of the maximum time.