AT_utpc2020_f Save Your MP

[problemUrl]: https://atcoder.jp/contests/utpc2020/tasks/utpc2020_f あなたは、魔物の群れに遭遇しました。群れは $ N $ 種類の魔物により構成されていて、 $ i $ 種類目の魔物が $ A_i $ 匹います。 あなたは、以下の $ 2 $ 種類のスキルを使い分けることによって、全ての魔物を倒すことにしました。 - スキル $ 1 $ : 魔力を $ X $ 消費する。魔物を $ K $ 匹まで選び、倒す。ただし、選ぶ魔物は全て **同じ** 種類である必要がある。 - スキル $ 2 $ : 魔力を $ Y $ 消費する。魔物を $ K $ 匹まで選び、倒す。ただし、選ぶ魔物は全て **違う** 種類である必要がある。 全ての魔物を倒すために消費する必要がある魔力の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ X $ $ Y $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $

答えを $ 1 $ 行に出力せよ。

### 制約 - 入力は全て整数である。 - $ 1\ \leq\ K\ \leq\ N\ \leq\ 10^5 $ - $ 1\ \leq\ X,\ Y\ \leq\ 10^5 $ - $ 1\ \leq\ A_i\ \leq\ 10^5 $ ### Sample Explanation 1 種類 $ 1 $ から 種類 $ 4 $ までの魔物が $ 1 $ 匹ずつと、種類 $ 5 $ の魔物が $ 2 $ 匹います。 次のようにスキルを使うことで、$ 40 $ の消費魔力で魔物を倒すことができます。 - 種類 $ 1 $ の魔物と 種類 $ 2 $ の魔物にスキル $ 2 $ を使う。魔力を $ 15 $ 消費する。 - 種類 $ 3 $ の魔物と 種類 $ 4 $ の魔物にスキル $ 2 $ を使う。魔力を $ 15 $ 消費する。 - 種類 $ 5 $ の魔物 $ 2 $ 匹にスキル $ 1 $ を使う。魔力を $ 10 $ 消費する。 これよりも少ない消費魔力で全ての魔物を倒すことはできないため、 $ 40 $ が答えとなります。 ### Sample Explanation 2 この場合は、次のようにスキルを使うことで、$ 30 $ の消費魔力で魔物を倒すことができます。 - 種類 $ 1 $ の魔物と 種類 $ 2 $ の魔物にスキル $ 2 $ を使う。魔力を $ 10 $ 消費する。 - 種類 $ 3 $ の魔物と 種類 $ 5 $ の魔物にスキル $ 2 $ を使う。魔力を $ 10 $ 消費する。 - 種類 $ 4 $ の魔物と 種類 $ 5 $ の魔物にスキル $ 2 $ を使う。魔力を $ 10 $ 消費する。 これよりも少ない消費魔力で全ての魔物を倒すことはできないため、 $ 30 $ が答えとなります。 ### Sample Explanation 3 この場合は、次のようにスキルを使うことで、$ 50 $ の消費魔力で魔物を倒すことができます。 - 種類 $ 1 $ の魔物にスキル $ 1 $ を使う。魔力を $ 10 $ 消費する。 - 種類 $ 2 $ の魔物にスキル $ 1 $ を使う。魔力を $ 10 $ 消費する。 - 種類 $ 3 $ の魔物にスキル $ 1 $ を使う。魔力を $ 10 $ 消費する。 - 種類 $ 4 $ の魔物にスキル $ 1 $ を使う。魔力を $ 10 $ 消費する。 - 種類 $ 5 $ の魔物 $ 2 $ 匹にスキル $ 1 $ を使う。魔力を $ 10 $ 消費する。 これよりも少ない消費魔力で全ての魔物を倒すことはできないため、 $ 50 $ が答えとなります。