You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时空限制

1S/512M

题目描述

apiadu 要参加一个答题比赛，比赛共有 $n$ 道题，答对第 $i$ 道题会得到 $a_i$ 分。

apiadu 知道所有题目的答案，但是他决定只回答其中 $m$ 道题，剩下的题目跳过。

当 apiadu 连续跳过多道题目时，其中跳过的前 $k$ 道题每道扣 $b$ 分，其余每道扣 $c$ 分。

比如当 $k=4$ 时，如果连续跳过 $5$ 道题总共会扣 $4\times b+ 1\times c$ 分，如果连续跳过 $2$ 道题总共会扣 $2\times b$ 分。

求最终总得分最大是多少。

格式

输入格式

第一行包含两个整数 $n,m$，分别表示题目的总数量和 apiadu 决定回答的题目数量。

第二行包含 $n$ 个整数 $a_i$，分别表示每道题目的分数。

第三行包含三个整数 $k,b,c$，表示连续跳过多道题目时，跳过的前 $k$ 道题每道扣 $b$ 分，其余每道扣 $c$ 分。

输出格式

输出一个整数表示最终总得分的最大值。

样例

样例输入 #1

8 2
1 3 2 1 6 4 1 1
1 1 100

样例输出 #1

-294

样例解释 #1

使得最终总得分最大的其中一种答题方案为：回答第 $2,5$ 道题，总得分为 $(-1)+3+(-1)+(-100)+6+(-1)+(-100)+(-100)=-294$。

数据规模

对于 $20\%$ 的数据，$n\leq 200$。

另有 $10\%$ 的数据，$k=1$。

另有 $10\%$ 的数据，$b=c$。

对于 $100\%$ 的数据，$1\leq m\leq n\leq 6000$，$1\leq a_i\leq 10^4$，$1\leq k\leq n$，$1\leq b\leq c\leq 10^4$。