C - 節制 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

セキュリティ意識が高く、最新鋭の錠を購入した高橋君ですが、財布の管理は甘かったらしくお金がピンチな状況です。

高橋君の収入は安定せず、次の収入があるのは今から N 日後です。高橋君は N 日間、できるだけ食費を抑えて節約生活を送ることにしました。

はじめ、高橋君の満腹度は H です。N 日間のそれぞれの日について、その日にとる食事を次の 3 種類の中から 1 つ選びます。

  • 普通の食事: A 円の出費をして、満腹度が B 増える。
  • 質素な食事: C 円の出費をして、満腹度が D 増える。（ただし、C < A かつ D < B）
  • 食事抜き: 出費なしで、満腹度が E 減る。

厳しく節約すれば出費を抑えることができますが、あまりに節約しすぎて体調を崩してしまってはいけないため、N 日間で一度も満腹度が 0 以下にならないようにしなければなりません。

高橋君は最低何円の食費で N 日間を乗り切ることができるでしょうか？

ただし、高橋君は超人級の胃袋を持っており、その満腹度には上限がないとする。すなわち、いくら食事をしても高橋君の満腹度が頭打ちになることはない。

入力

入力は以下の形式で標準入力から与えられる。

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 < A\,≦\,10^6 が成り立つ。
    • 満腹度の増減について、1\,≦\,D < B\,≦\,10^6 および 1\,≦\,E\,≦\,10^6 が成り立つ。

部分点

この問題には部分点が設定されている。

  • N\,≦\,10 を満たすテストケース全てに正解すると、部分点として 10 点が与えられる。
  • N\,≦\,50, H\,≦\,50, B\,≦\,50, D\,≦\,50 を満たすテストケースすべてに正解すると、部分点として 30 点が与えられる。（N\,≦\,10 を満たすテストケース全てにも正解していた場合は合計で 40 点となる）
  • N\,≦\,1,000 を満たすテストケース全てに正解すると、100 点が与えられる。
  • 全てのテストケースに正解すると、ボーナス点として追加で 1 点が与えられる。

ボーナス点に対応するテストケースに関しては、答えが 32 ビットの整数型に収まらない可能性があることに注意せよ。

出力

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

出力の末尾には改行をいれること。

入力例1

4 5
100 4 60 1 4

出力例1

160

たとえば、4 日間の食事を以下のようにすれば 160 円の出費で済ませることができます。

  • 節約生活を始める前、高橋君の満腹度は 5 である。
  • 1 日目には質素な食事をとる。60 円を出費して、満腹度が 1 増えて 6 になる。
  • 2 日目は食事を抜く。出費はなく、満腹度は 4 減って 2 になる。
  • 3 日目には普通の食事をとる。100 円を出費して、満腹度が 4 増えて 6 になる。
  • 4 日目は食事を抜く。出費はなく、満腹度は 4 減って 2 になる。

入力例2

10 1
5000 2 2000 1 300

出力例2

20000

この例では、高橋君は 1 日食事を抜くと満腹度が 300 も減ってしまうので、毎日食事をとる必要があります。

質素な食事を 10 日間とり続けることで 2,000 \times 10 = 20,000 円の出費となり、これが最小の出費になります。

入力例3

9 23
170 8 120 5 12

出力例3

650

入力例4

653 314159
6728 123456 5141 41928 222222

出力例4

2818162

この例は N\,≦\,10 という 10 点の部分点の制約および N\,≦\,50, H\,≦\,50, B\,≦\,50, D\,≦\,50 という 30 点の部分点の制約を満たしていないことに注意せよ。