/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
問題文
アイテムを買って使うことで、体力 H の敵を倒すゲームをします。アイテムは以下の 2 種類です。
-
アイテム 1： 使うと敵の体力を A 減らします。値段は B 円です。
-
アイテム 2： 使うと敵の体力を C 減らします。体力を C 減らした後の敵の体力を h として、h>0 ならばさらに敵の体力を \lfloor \frac{h}{2}\rfloor 減らします。値段は D 円です。ここで、\lfloor A \rfloor は A の小数点以下を切り捨てた値を指します。
アイテムは使い切りであり 1 回使うと消えてしまいますが、好きな個数買うことができます。また、使う順番は自由です。
敵の体力を 0 以下にするために必要なお金の最小値を求めてください。
制約
- 1\leq H,A,B,C,D \leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
H A B C D
出力
答えを出力せよ。
入力例 1
13 6 5 1 7
出力例 1
12
アイテム 1 を 1 個、アイテム 2 を 1 個買い、以下の順番で使います。
-
アイテム 2 を使う。敵の体力は 1 減り、12 となる。さらに敵の体力は \lfloor \frac{12}{2}\rfloor=6 減り、 6 となる。
-
アイテム 1 を使う。敵の体力は 6 減り、0 となる。
これで敵の体力を 0 以下にすることができました。必要なお金の合計は、 5 + 7 = 12 円であり、これが最小値であることが証明可能です。
入力例 2
1000 1 1 1 10000
出力例 2
1000
Problem Statement
You are playing a game, where you buy and use items to beat an enemy with stamina H. There are two kinds of items.
-
Item 1: when you use it, the enemy's stamina is reduced by A. The price is B yen (the currency in Japan).
-
Item 2: when you use it, the enemy's stamina is reduced by C. Let h be the resulting stamina. Then, if h>0, the enemy's stamina is further reduced by \lfloor \frac{h}{2}\rfloor, where \lfloor A \rfloor denotes the value A rounded down to an integer.
An item disappears once you use it, but you may buy any number of the items. Also, you may use items in any order.
Find the minimum amount of money required to make the enemy's stamina 0 or less.
Constraints
- 1\leq H,A,B,C,D \leq 10^9
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
H A B C D
Output
Print the answer.
Sample Input 1
13 6 5 1 7
Sample Output 1
12
You can buy one item 1 and one item 2 and use them in the following order:
-
Use item 2 to reduce the enemy's stamina by 1, making it 12. Then, the enemy's stamina is further reduced by \lfloor \frac{12}{2}\rfloor=6 and becomes 6.
-
Use item 1 to reduce the enemy's stamina by 6, making it 0.
This way, you can make the enemy's stamina 0 or less. The total amount of money required is 5 + 7 = 12, which we can prove is the minimum.
Sample Input 2
1000 1 1 1 10000
Sample Output 2
1000