WC '16 Finals S1 - Cow-Bot Construction - Olympiads Online Judge

WC '16 Finals S1 - Cow-Bot Construction

Points: 7 (partial)

Time limit: 1.4s

Memory limit: 32M

Author:

Problem type

2016-17 Woburn Challenge Finals Round - Senior Division

It would seem that war is inevitable. Bo Vine's communication with his cow spy has been intercepted by the devious monkeys, confirming his suspicions that the Head Monkey is up to no good! In preparation for the impending conflict with the monkeys, Bo Vine has ordered the construction of a new, state-of-the-art Cow-Bot model from scratch.

The schematics call for $N$ $N$ $(1 \le N \le 200\,000)$ $(1 \leq N \leq 200 000)$ different modules to be installed, in any order. Bo Vine's cow engineers require $E$ $E$ $(1 \le E \le 10\,000)$ $(1 \leq E \leq 10 000)$ minutes to install any single module. However, the Cow-Bot (being a sophisticated, artificially intelligent piece of hardware) may also be able to help out! If at least $M_i$ $M_{i}$ $(0 \le M_i \le N)$ $(0 \leq M_{i} \leq N)$ different modules have already been installed into the Cow-Bot up to a certain point in time, then it becomes able to install the $i$ $i$ -th module into itself in $B$ $B$ $(1 \le B \le 10\,000)$ $(1 \leq B \leq 10 000)$ minutes. Only one module may be in the process of being installed into the Cow-Bot at any time, meaning that the engineers and Cow-Bot may not simultaneously install two different modules at once.

Please help the cows determine the minimum amount of time required for all $N$ $N$ modules to be installed into the Cow-Bot.

In test cases worth $7/9$ $7 / 9$ of the points, $N \le 2\,000$ $N \leq 2 000$ .

Input Specification

The first line of input consists of three space-separated integers $N$ $N$ , $E$ $E$ , and $B$ $B$ .
$N$ $N$ lines follow, the $i$ $i$ -th of which consists of a single integer $M_i$ $M_{i}$ (for $i = 1 \dots N$ $i = 1 \dots N$ ).

Output Specification

Output one line consisting of a single integer – the minimum number of minutes required for all $N$ $N$ modules to be installed into the Cow-Bot.

Sample Input

Copy

Sample Output

Copy

Sample Explanation

One optimal sequence of module installations is as follows (with each step's completion time indicated):

Module $2$ $2$ by the Cow-Bot ( $4$ $4$ minutes)
Module $3$ $3$ by the engineers ( $11$ $11$ minutes)
Module $7$ $7$ by the engineers ( $18$ $18$ minutes)
Module $4$ $4$ by the Cow-Bot ( $22$ $22$ minutes)
Module $6$ $6$ by the Cow-Bot ( $26$ $26$ minutes)
Module $1$ $1$ by the Cow-Bot ( $30$ $30$ minutes)
Module $5$ $5$ by the Cow-Bot ( $34$ $34$ minutes)

Comments

There are no comments at the moment.