今晚有个派对，但饮料还没准备好！你打算为朋友们准备鸡尾酒。鸡尾酒由 $n$ 种不同的配料组成。你面前有 $n$ 个罐子，从左到右依次编号为 $1$ 到 $n$。每个罐子里都装有一种配料。你需要将每个罐子里的配料分别搅拌均匀。

手动搅拌第 $i$ 个罐子里的内容物需要 $a_i$ 秒。此外，你还有一个功能强大的搅拌机，可以在 $B$ 秒内搅拌任意 $k$ 个连续罐子里的内容物（搅拌机可以使用任意多次）。最后，你可以在 $C$ 秒内交换任意两个罐子的位置（这两个罐子不需要相邻）。允许对任何罐子里的内容物进行多次搅拌。

请问将所有 $n$ 个罐子里的配料都搅拌均匀所需的最短时间是多少？只要所有罐子都被搅拌过，罐子的最终顺序并不重要。

输入格式

第一行包含四个用空格分隔的整数 $n, k, B, C$ ($1 \le k \le n \le 500$, $1 \le B, C \le 10\,000$)，分别表示罐子的数量、搅拌机的覆盖范围、使用搅拌机所需的时间以及交换两个罐子所需的时间。

第二行包含 $n$ 个用空格分隔的整数 $a_1, \dots, a_n$ ($1 \le a_i \le 10\,000$)，其中 $a_i$ 表示手动搅拌第 $i$ 个罐子里的内容物所需的时间。

输出格式

输出一个整数，表示将所有罐子里的内容物搅拌均匀所需的最短时间。

样例

样例输入 1

5 2 10 3
10 1 20 2 3

样例输出 1

19