No.1071 Behomara
タグ : / 解いたユーザー数 245
作問者 :
Kiri8128
/ テスター :
nmnmnmnmnmnmnm
Problem Statement
You are on an adventure with $N$ companions.
Each companion has a stat called HP representing their stamina, and initially the HP of every companion is 1.
Each companion also has a fixed upper limit on HP, called "Max HP", and their HP can be restored up to Max HP.
Your role is to restore the HP of all companions to their Max HP.
You have learned two healing spells, and you may cast them any number of times in any order.
Casting a spell consumes magic power called MP. You have enough MP, so it will never run out along the way.
The healing spells you have learned, their effects, and their MP costs are as follows.
- Behoimi Choose one specific companion and restore that companion's HP by $K$. However, HP is restored only up to Max HP (see Sample 1 for details).
Each cast consumes $X$ MP.
- Behomara Restores the HP of all companions by $K$. However, HP is restored only up to Max HP (see Sample 1 for details).
Each cast consumes $Y$ MP.
Input
The input is given in 2 lines.The first line contains $N$ (the number of companions), $K$ (the amount healed by the healing spells), $X$ (the MP consumed by Behoimi), and $Y$ (the MP consumed by Behomara), separated by spaces.
The second line contains $A_i$, the Max HP of the $i\ (1\le i \le N)$-th companion, separated by spaces.
$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)$
All inputs are integers.
Output
Output the minimum MP that must be consumed to restore the HP of all companions to their Max HP.
Sample
Sample 1
Input
3 50 2 3 81 101 121
Output
8
Initially, the companions' HP values are 1, 1, 1 in order.
First, casting Behomara for MP 3 makes the companions' HP 51, 51, 51 in order.
Casting Behomara once more for MP 3 makes the companions' HP 81, 101, 101 in order. (Note that the 1st companion's Max HP is 81, so their HP is restored only up to that value.)
Next, casting Behoimi on the 3rd companion for MP 2 makes the companions' HP 81, 101, 121 in order. (Note that the 3rd companion's Max HP is 121, so their HP is restored only up to that value.)
The total MP consumed here is 8. No method consumes less MP, so output 8.
Sample 2
Input
5 20 1 1000000000 21 41 61 81 101
Output
15
Behomara is inefficient.
Sample 3
Input
5 20 1000000000 1 21 41 61 81 101
Output
5
This can happen too.
Sample 4
Input
3 100 10 20 1 1 1
Output
0
Everyone is at full HP from the start.
Sample 5
Input
6 123 21 53 36899968 15071320 97202973 20995418 15845307 64054313
Output
30831756
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。