Woburn Challenge 2016-17 Round 3 - Junior Division

Problem 1: The Elite N

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 ≤ N ≤ 109). 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 Pokeball. 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 ≤ S ≤ 109) seconds. You'll then use your currently active Pokémon to battle against the next of the N trainers. It takes Aeroxis A (1 ≤ A ≤ 109) seconds to defeat a trainer, and it takes Brinoble B (1 ≤ B ≤ 109) 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 ≤ M ≤ 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 Ti of the Elite N. The numbers T1..M are distinct, and are given in increasing order (1 ≤ T1 < T2 < … < TM ≤ 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 ≤ 105.

Input Format

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, Ti (for i = 1..M).

Output Format

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 1st battle (5 seconds).
  • Use Brinboble for battles 1..4 (8 seconds).
  • Swap to Aeroxis (5 seconds).
  • Use Aeroxis for batles 5..6 (10 seconds).
  • Swap to Brinboble (5 seconds).
  • Use Brinboble for battles 7..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..16 (10 seconds).
  • Swap to Aeroxis (5 seconds).
  • Use Aeroxis for battles 17..20 (20 seconds).

All Submissions
Best Solutions


Point Value: 7 (partial)
Time Limit: 1.00s
Memory Limit: 64M
Added: Feb 19, 2017
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...