問題一覧 > 通常問題

No.1071 ベホマラー

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 203
作問者 : Kiri8128Kiri8128 / テスター : nmnmnmnmnmnmnmnmnmnmnmnmnmnm
9 ProblemId : 4371 / 出題時の順位表
問題文最終更新日: 2020-05-17 23:04:02

問題文

あなたは $N$ 人の仲間と冒険をしています。 仲間にはそれぞれ体力を表す HP というステータスがあり、最初すべての仲間の HP は 1 です。 またそれぞれの仲間には HP の取りうる上限「さいだいHP」が決まっていて、 HP は さいだいHP まで回復することができます。 あなたの役割は、仲間全員の HP を さいだいHP まで回復することです。
あなたは2つの回復呪文を覚えていて、これらを好きな順番に何度でも唱えることができます。 呪文を唱えるには MP という魔力を消費します。あなたの MP は十分にあるので途中で枯渇することはありません。
あなたが覚えている回復呪文とその効果、消費する MP は下記のとおりです。

  • ベホイミ
  • 特定の仲間1人を選んで その仲間の HP を $K$ だけ回復します。ただし HP は さいだいHP までしか回復しません(詳しくはサンプル1を見てください)。
    1回唱えるごとに MP を $X$ だけ消費します。
  • ベホマラー
  • 仲間全員 の HP を $K$ だけ回復します。ただし HP は さいだいHP までしか回復しません(詳しくはサンプル1を見てください)。
    1回唱えるごとに MP を $Y$ だけ消費します。
これらの呪文以外の方法で仲間の HP を回復させることはできません。仲間全員の HP を さいだいHP まで回復させるために消費する MP の最小値を求めてください。

入力

入力は2行で与えられます。
1行目には $N$ (仲間の人数)、 $K$ (回復呪文の回復量)、 $X$ (ベホイミが消費する MP )、 $Y$ (ベホマラーが消費する MP )が空白区切りで与えられます。
2行目には $i\ (1\le i \le N)$ 番目の仲間の さいだいHP を表す $A_i$ が空白区切りで与えられます。

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

$1\le N \le 10^5$
$1\le K,\ X,\ Y \le 10^9$
$1\le A_i\le 10^9\ (1\le i \le N)$
入力はすべて整数

出力

仲間全員の HP を さいだいHP まで回復させるために消費する MP の最小値を出力してください。

サンプル

サンプル1
入力
3 50 2 3
81 101 121
出力
8

最初、仲間の HP は順に 1, 1, 1 です。
まず MP 3 を消費してベホマラーを唱えると、仲間の HP は順に 51, 51, 51 になります。
もう一度 MP 3 を消費してベホマラーを唱えると、仲間の HP は順に 81, 101, 101 になります。(1番目の仲間は さいだいHP が81なので、そこまでしか回復しないことに注意してください。)
次に MP 2 を消費して3番目の仲間にベホイミを唱えると仲間の HP は順に 81, 101, 121 になります。(3番目の仲間は さいだいHP が121なので、そこまでしか回復しないことに注意してください。)
このとき消費する MP の合計は8です。これより消費 MP の少ない方法は存在しないので、8を出力してください。

サンプル2
入力
5 20 1 1000000000
21 41 61 81 101
出力
15

ベホマラーは非効率です。

サンプル3
入力
5 20 1000000000 1
21 41 61 81 101
出力
5

こういうこともあります。

サンプル4
入力
3 100 10 20
1 1 1
出力
0

最初からまんたんです。

サンプル5
入力
6 123 21 53
36899968 15071320 97202973 20995418 15845307 64054313
出力
30831756

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。