問題文

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

高橋君の収入は安定せず、次の収入があるのは今から $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$ 点の部分点の制約を満たしていないことに注意せよ。

---