問題文
你遭遇了一群魔物。群体由 N 种魔物组成。 i 种类的魔物有 A_i 有。
你打算通过以下 2 种类的技能交替使用,来打倒所有魔物。
- 技能 1 :魔力为 X 消耗魔力。选择魔物至多 K 只进行击倒。但是,选择的魔物必须全部是 相同
您可以使用任意数量的 种类。
- 技能 2 :魔力为 Y 消耗魔力。选择魔物至多 K 只进行击倒。但是,选择的魔物必须全部是 不同的 种类。
请计算为了打倒所有魔物而必须消耗的最小魔力。
制約
- 所有输入均为整数。
- 1 \leq K \leq N \leq 10^5
- 1 \leq X, Y \leq 10^5
- 1 \leq A_i \leq 10^5
入力
输入是按以下格式从标准输入给出的。
N K X Y A_1 A_2 \cdots A_N
出力
答案 请打印除以 1 行输出。
入力例 1
5 2 10 15 1 1 1 1 2
出力例 1
40
種類 1 从 种类 4 到 魔物有 1 只每种,种类 5 的魔物有 2 有。
通过如下使用技能,40 的消耗魔力可以击倒魔物。
- 種類 1 的魔物和 种类 2 的魔物使用技能 2 。魔力为 15 消耗。
- 種類 3 的魔物和 种类 4 的魔物使用技能 2 。魔力为 15 消耗。
- 種類 5 的魔物 2 匹配技能 1 。魔力为 10 消耗。
由于无法以更少的魔力消耗击败所有魔物, 40 就是答案。
入力例 2
5 2 15 10 1 1 1 1 2
出力例 2
30
在这种情况下,通过如下方式使用技能,30 的消耗魔力可以击倒魔物。
- 種類 1 的魔物和 种类 2 的魔物使用技能 2 。魔力为 10 消耗。
- 種類 3 的魔物和 种类 5 的魔物使用技能 2 。魔力为 10 消耗。
- 種類 4 的魔物和 种类 5 的魔物使用技能 2 。魔力为 10 消耗。
由于无法以更少的魔力消耗击败所有魔物, 30 就是答案。
入力例 3
5 2 10 25 1 1 1 1 2
出力例 3
50
在这种情况下,通过如下方式使用技能,50 的消耗魔力可以击倒魔物。
- 種類 1 的魔物使用技能 1 。魔力为 10 消耗。
- 種類 2 的魔物使用技能 1 。魔力为 10 消耗。
- 種類 3 的魔物使用技能 1 。魔力为 10 消耗。
- 種類 4 的魔物使用技能 1 。魔力为 10 消耗。
- 種類 5 的魔物 2 匹配技能 1 。魔力为 10 消耗。
由于无法以更少的魔力消耗击败所有魔物, 50 就是答案。