AT_utpc2020_f.Save Your MP

你遇到了一群魔物。这群魔物由 $N$ 种不同类型的魔物组成，第 $i$ 种魔物有 $A_i$ 只。

你可以通过以下两种技能来击败所有魔物：

• 技能 $1$：消耗 $X$ 点魔力。你可以选择至多 $K$ 只魔物并击败它们，但所选的魔物必须全部属于同一种类型。
• 技能 $2$：消耗 $Y$ 点魔力。你可以选择至多 $K$ 只魔物并击败它们，但所选的魔物必须全部属于不同的类型。

请你求出击败所有魔物所需消耗的最小魔力值。

输入通过标准输入按以下格式给出。

$N$ $K$ $X$ $Y$ $A_1$ $A_2$ $\cdots$ $A_N$

输出一个整数，表示击败所有魔物所需消耗的最小魔力值。

限制条件

• 所有输入均为整数。
• $1 \leq K \leq N \leq 10^5$
• $1 \leq X, Y \leq 10^5$
• $1 \leq A_i \leq 10^5$

样例解释 1

第 $1$ 到第 $4$ 种魔物各有 $1$ 只，第 $5$ 种魔物有 $2$ 只。可以如下使用技能，总共消耗 $40$ 点魔力击败所有魔物：

• 对第 $1$ 种和第 $2$ 种魔物使用技能 $2$，消耗 $15$ 点魔力。
• 对第 $3$ 种和第 $4$ 种魔物使用技能 $2$，消耗 $15$ 点魔力。
• 对第 $5$ 种的 $2$ 只魔物使用技能 $1$，消耗 $10$ 点魔力。
  无法用更少的魔力击败所有魔物，因此答案为 $40$。

样例解释 2

在这种情况下，可以如下使用技能，总共消耗 $30$ 点魔力击败所有魔物：

• 对第 $1$ 种和第 $2$ 种魔物使用技能 $2$，消耗 $10$ 点魔力。
• 对第 $3$ 种和第 $5$ 种魔物使用技能 $2$，消耗 $10$ 点魔力。
• 对第 $4$ 种和第 $5$ 种魔物使用技能 $2$，消耗 $10$ 点魔力。
  无法用更少的魔力击败所有魔物，因此答案为 $30$。

样例解释 3

在这种情况下，可以如下使用技能，总共消耗 $50$ 点魔力击败所有魔物：

• 对第 $1$ 种魔物使用技能 $1$，消耗 $10$ 点魔力。
• 对第 $2$ 种魔物使用技能 $1$，消耗 $10$ 点魔力。
• 对第 $3$ 种魔物使用技能 $1$，消耗 $10$ 点魔力。
• 对第 $4$ 种魔物使用技能 $1$，消耗 $10$ 点魔力。
• 对第 $5$ 种的 $2$ 只魔物使用技能 $1$，消耗 $10$ 点魔力。
  无法用更少的魔力击败所有魔物，因此答案为 $50$。

由 ChatGPT 4.1 翻译