← 返回题目列表

AtCoder · utpc2020_f

F. 保存你的 MP

中文机器翻译题面 查看原题

問題文

你遭遇了一群魔物。群体由 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 就是答案。