Problem Statement

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

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

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

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

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

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

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

Input

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

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$ ビットの整数型に収まらない可能性があることに注意せよ。

Output

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

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