Cross

题目描述

You need to maximize the total decrease in a target's Health Points (HP) over an $n$-round process. The total HP decrease can be negative (meaning the target's HP increased overall).

Initially, there are two parameters $r = 0$ and $c = 0$. Over the course of $n$ rounds, in round $i$ ($1 \le i \le n$), the following events occur sequentially:

1. The parameter $r$ is increased by $a_i$.
2. You may choose to use a skill. If you use the skill, $c$ is increased by $1$, and $r$ is decreased by $1$ (if $r = 0$, it cannot be decreased, but the skill can still be used and $c$ will still increase). Note that you can use this skill at most $K$ times across all $n$ rounds.
3. The target recovers $r \times R$ HP.
4. You deal $X$ fixed damage to the target.
5. The target takes $c \times C$ continuous damage.

You need to output the maximum possible total HP decrease.

Note that you do not care about the intermediate HP values during the process; you only care about the difference between the target's initial HP and final HP after all $n$ rounds.

输入格式

The first line contains $5$ integers $n, K, R, X, C$, representing the number of attack rounds, the maximum number of skill uses, the continuous HP recovery multiplier, the fixed damage per attack, and the continuous damage multiplier, respectively.

The second line contains $n$ non-negative integers. The $i$-th integer is $a_i$, representing the number of times the recovery effect is applied in round $i$.

For all testcases, $1 \le K \le n \le 2 \times 10^6$, $0 \le X, R, C, a_i \le 10^6$.

输出格式

Output a single integer, representing the maximum possible decrease in the target's HP.

样例输入 #1

5 3 1 2 3
1 0 2 0 0

样例输出 #1

43

样例输入 #2

5 3 3 3 4
0 1 0 4 4

样例输出 #2

29

样例输入 #3

8 1 9 2 8
0 0 0 1 1 10 10 10

样例输出 #3

-520