AT_abc013_3 [ABC013C] 節制

[problemUrl]: https://atcoder.jp/contests/abc013/tasks/abc013_3 セキュリティ意識が高く、最新鋭の錠を購入した高橋君ですが、財布の管理は甘かったらしくお金がピンチな状況です。 高橋君の収入は安定せず、次の収入があるのは今から $ N $ 日後です。高橋君は $ N $ 日間、できるだけ食費を抑えて節約生活を送ることにしました。 はじめ、高橋君の満腹度は $ H $ です。$ N $ 日間のそれぞれの日について、その日にとる食事を次の $ 3 $ 種類の中から $ 1 $ つ選びます。 - 普通の食事: $ A $ 円の出費をして、満腹度が $ B $ 増える。 - 質素な食事: $ C $ 円の出費をして、満腹度が $ D $ 増える。（ただし、$ C\

入力は以下の形式で標準入力から与えられる。 > $ N $ $ H $ $ A $ $ B $ $ C $ $ D $ $ E $ - $ 1 $ 行目には、節約生活の日数を表す整数 $ N $ ($ 1\,≦\,N\,≦\,5\ \times\ 10^5 $) と、節約生活を始める前の高橋君の満腹度を表す整数 $ H $ ($ 1\,≦\,H\,≦\,10^9 $) が空白区切りで与えられる。 - $ 2 $ 行目には、$ 3 $ 種類の食事に関する情報を表す整数 $ A $, $ B $, $ C $, $ D $, $ E $ がこの順に空白区切りで与えられる。 - 出費について、$ 1\,≦\,C\

高橋君が満腹度を一度も $ 0 $ 以下にせずに $ N $ 日間の節約生活を乗り切るために必要な食費の最小値が何円かを $ 1 $ 行に出力せよ。 出力の末尾には改行をいれること。

### 部分点 この問題には部分点が設定されている。 - $ N\,≦\,10 $ を満たすテストケース全てに正解すると、部分点として $ 10 $ 点が与えられる。 - $ N\,≦\,50 $, $ H\,≦\,50 $, $ B\,≦\,50 $, $ D\,≦\,50 $ を満たすテストケースすべてに正解すると、部分点として $ 30 $ 点が与えられる。（$ N\,≦\,10 $ を満たすテストケース全てにも正解していた場合は合計で $ 40 $ 点となる） - $ N\,≦\,1,000 $ を満たすテストケース全てに正解すると、$ 100 $ 点が与えられる。 - 全てのテストケースに正解すると、ボーナス点として追加で $ 1 $ 点が与えられる。 ボーナス点に対応するテストケースに関しては、答えが $ 32 $ ビットの整数型に収まらない可能性があることに注意せよ。 ### Sample Explanation 1 たとえば、$ 4 $ 日間の食事を以下のようにすれば $ 160 $ 円の出費で済ませることができます。 - 節約生活を始める前、高橋君の満腹度は $ 5 $ である。 - $ 1 $ 日目には質素な食事をとる。$ 60 $ 円を出費して、満腹度が $ 1 $ 増えて $ 6 $ になる。 - $ 2 $ 日目は食事を抜く。出費はなく、満腹度は $ 4 $ 減って $ 2 $ になる。 - $ 3 $ 日目には普通の食事をとる。$ 100 $ 円を出費して、満腹度が $ 4 $ 増えて $ 6 $ になる。 - $ 4 $ 日目は食事を抜く。出費はなく、満腹度は $ 4 $ 減って $ 2 $ になる。 ### Sample Explanation 2 この例では、高橋君は $ 1 $ 日食事を抜くと満腹度が $ 300 $ も減ってしまうので、毎日食事をとる必要があります。 質素な食事を $ 10 $ 日間とり続けることで $ 2,000\ \times\ 10\ =\ 20,000 $ 円の出費となり、これが最小の出費になります。 ### Sample Explanation 4 この例は $ N\,≦\,10 $ という $ 10 $ 点の部分点の制約および $ N\,≦\,50 $, $ H\,≦\,50 $, $ B\,≦\,50 $, $ D\,≦\,50 $ という $ 30 $ 点の部分点の制約を満たしていないことに注意せよ。