题目描述

小 Y 的朋友小 M 有 $n$ 个装有苹果的盘子，这些盘子排成一排。

从左往右第 $i$ 个盘子中有 $a_i$ 个苹果，现在小 M 想让所有苹果都被吃掉。

小 M 可以执行任意多次操作，每次选择以下三种操作之一：

• 选择一个仍有苹果的盘子，并吃掉该盘子内的所有苹果，每吃掉一个苹果花费 $1$ 体力。
• 选择一个整数 $i$ 满足 $1\le i\le n-k+1$，花费 $X$ 的体力请小 Y 吃掉第 $i,i+1,\dots,i+k-1$ 个盘子中当前剩余的所有苹果。
• 选择两个整数 $i,j$ 满足 $1\le i<j\le n$，花费 $C$ 的体力交换从左往右第 $i$ 个盘子和第 $j$ 个盘子中的全部苹果，即让两个盘子中剩余的苹果数互换。

你只需要帮她计算出至少要花费多少体力才能让所有苹果都被吃掉。

输入格式

从文件 apple.in 中读入数据。

第一行四个整数 $n,k,X,C$，表示盘子的数量，第二种操作中选择盘子的数量，执行一次第二种操作所需的体力，以及执行一次第三种操作所需的体力。

第二行 $n$ 个整数，第 $i$（$1\le i\le n$）个为 $a_i$，表示初始从左往右第 $i$ 个盘子中的苹果数量。

输出格式

输出到文件 apple.out 中。

输出一行一个整数，表示使所有苹果都被吃掉所需的最小体力。

样例 1 输入

4 2 5 2
5 1 1 6

样例 1 输出

9

样例 1 解释

小 M 可以花费 $2$ 体力，交换第 $2,4$ 个盘子，然后花费 $5$ 体力让小 Y 吃掉第 $1,2$ 个盘子中的所有苹果，最后，小 M 分别吃掉第 $3$ 个和第 $4$ 个盘子中剩余的苹果，共花费 $2$ 体力。

样例 2

见选手目录下的 apple/apple2.in 与 apple/apple2.ans。

该样例满足子任务 $1$ 的约束条件。

样例 3

见选手目录下的 apple/apple3.in 与 apple/apple3.ans。

该样例满足子任务 $2$ 的约束条件。

样例 4

见选手目录下的 apple/apple4.in 与 apple/apple4.ans。

该样例满足子任务 $3$ 的约束条件。

样例 5

见选手目录下的 apple/apple5.in 与 apple/apple5.ans。

该样例满足子任务 $4$ 的约束条件。

样例 6

见选手目录下的 apple/apple6.in 与 apple/apple6.ans。

该样例满足子任务 $5$ 的约束条件。

样例 7

见选手目录下的 apple/apple7.in 与 apple/apple7.ans。

该样例满足子任务 $6$ 的约束条件。

数据范围

对于所有测试数据，保证 $1\le k\le n\le 500$，$1\le a_i,X,C\le 10^6$。

特殊性质 A：对于所有 $1\le i\le n$，均有 $a_i\le C$。