問題文

あなたは、魔物の群れに遭遇しました。群れは 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

入力例 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 が答えとなります。