問題一覧 > 通常問題

No.1071 ベホマラー

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 244
作問者 : Kiri8128 / テスター : nmnmnmnmnmnmnm
14 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≤i≤N) 番目の仲間の さいだいHP を表す Ai が空白区切りで与えられます。

N K X Y
A1 A2  ⋯ AN

1≤N≤105
1≤K, X, Y≤109
1≤Ai≤109 (1≤i≤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もしくは右上の雲マークをクリックしてアカウントを作成してください。