Problem Description

Takahashi, who has a high security awareness and has purchased the latest lock, seems to be poor at managing his wallet, and is currently in a financial pinch.

Takahashi's income is unstable, and his next income will be in $ N $ days from now. Takahashi decided to live a frugal life for $ N $ days, trying to minimize his food expenses as much as possible.

Initially, Takahashi's fullness level is $ H $. For each of the $ N $ days, he will choose one of the following three types of meals:

• Regular meal: Costs $ A $ yen and increases fullness by $ B $.
• Simple meal: Costs $ C $ yen and increases fullness by $ D $. (However, $ C < A $ and $ D < B $)
• No meal: No cost, and fullness decreases by $ E $.

While it is possible to reduce expenses by being strict with frugality, he must not compromise his health by being too frugal. Therefore, he must ensure that his fullness level never drops to $ 0 $ or below during the $ N $ days.

What is the minimum amount of food expenses Takahashi can incur to get through the $ N $ days without letting his fullness level drop to $ 0 $ or below?

Note that Takahashi has a superhuman stomach and his fullness level has no upper limit. That is, no matter how much he eats, his fullness level will not cap out.

Input Format

The input is given from the standard input in the following format:

$ N $ $ H $ $ A $ $ B $ $ C $ $ D $ $ E $

• The first line contains the integer $ N $ ($1 \leq N \leq 5 \times 10^5$) representing the number of days of the frugal life and the integer $ H $ ($1 \leq H \leq 10^9$) representing Takahashi's initial fullness level, separated by spaces.
• The second line contains the integers $ A $, $ B $, $ C $, $ D $, and $ E $ in that order, separated by spaces, representing the information about the three types of meals.
• For the expenses, $1 \leq C < A \leq 10^6$ holds.
• For the fullness changes, $1 \leq D < B \leq 10^6$ and $1 \leq E \leq 10^6$ hold.

Output Format

Output the minimum amount of food expenses Takahashi needs to get through the $ N $ days without letting his fullness level drop to $ 0 $ or below in one line.

End the output with a newline.

Sample Input and Output

Sample Input #1

4 5
100 4 60 1 4

Sample Output #1

160

Sample Input #2

10 1
5000 2 2000 1 300

Sample Output #2

20000

Sample Input #3

9 23
170 8 120 5 12

Sample Output #3

650

Sample Input #4

653 314159
6728 123456 5141 41928 222222

Sample Output #4

2818162

Notes/Hints

Partial Points

This problem has partial points.

• Correctly solving all test cases where $N \leq 10$ will award $ 10 $ points.
• Correctly solving all test cases where $N \leq 50$, $H \leq 50$, $B \leq 50$, and $D \leq 50$ will award $ 30 $ points. (If all test cases where $N \leq 10$ are also solved, the total will be $ 40 $ points)
• Correctly solving all test cases where $N \leq 1,000$ will award $ 100 $ points.
• Correctly solving all test cases will award an additional $ 1 $ bonus point.

Note that for the test cases corresponding to the bonus point, the answer may not fit within a 32-bit integer type.

Sample Explanation 1

For example, if Takahashi arranges his meals for the 4 days as follows, he can manage with $ 160 $ yen in expenses:
- At the start of the frugal life, Takahashi's fullness level is $ 5 $.
- On the 1st day, he has a simple meal. He spends $ 60 $ yen, and his fullness increases by $ 1 $ to $ 6 $.
- On the 2nd day, he skips a meal. There is no expense, and his fullness decreases by $ 4 $ to $ 2 $.
- On the 3rd day, he has a regular meal. He spends $ 100 $ yen, and his fullness increases by $ 4 $ to $ 6 $.
- On the 4th day, he skips a meal. There is no expense, and his fullness decreases by $ 4 $ to $ 2 $.

Sample Explanation 2

In this example, since skipping a meal would decrease Takahashi's fullness by $ 300 $, he needs to eat every day. Continuing to have simple meals for 10 days results in $2,000 \times 10 = 20,000$ yen in expenses, which is the minimum.

Sample Explanation 4

Note that this example does not satisfy the constraints for the $ 10 $ points partial point ($N \leq 10$) and the $ 30 $ points partial point ($N \leq 50$, $H \leq 50$, $B \leq 50$, $D \leq 50$).

见题面 Input 部分

见题面 Output 部分