No.1071 ベホマラー
タグ : / 解いたユーザー数 242
作問者 :
Kiri8128
/ テスター :
nmnmnmnmnmnmnm
問題文
あなたは $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$ だけ消費します。
入力
入力は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もしくは右上の雲マークをクリックしてアカウントを作成してください。