Background

For special reasons, the other $24$ testdata sets of this problem should be submitted here.

Valentine always wins.

Problem Description

Valentine wants to buy roses for his $N$ girlfriends. There are two shops in front of him. Each shop has an unlimited number of roses, but they sell roses only in bundles. In the first shop, each bundle contains $A$ roses and costs $B$ money. In the second shop, each bundle contains $C$ roses and costs $D$ money.

Find the minimum amount of money Valentine needs to spend to buy at least $N$ roses.

You can understand it like this: if $M > N$ but buying $M$ roses costs less than buying $N$ roses, then Valentine will buy $M$ roses and give the extra roses to other girls. Yes, Valentine is very “playboy” (huaxin).

Input Format

One line with five integers $N, A, B, C, D$, with meanings as described in the statement.

Output Format

One line with one integer representing the minimum cost.

5 1 4 3 6

12

22 2 3 10 14

31

Hint

Sample Explanation

For sample $1$, Valentine can choose to buy $2$ bundles from the second shop.

For sample $2$, Valentine can choose to buy $1$ bundle from the first shop and $2$ bundles from the second shop.

Constraints

This problem uses bundled tests.

• Subtask 1 (20 pts): $N, A, B, C, D \le 1000$.
• Subtask 2 (80 pts): no special restrictions.

For $100\%$ of the data, $1 \le N \le 10^{15}$, $1 \le A, B, C, D \le 10^5$, and it is guaranteed that the answer does not exceed $10^{18}$.

Notes

Translated from BalticOI 2020 Day0 B Roses.

It is the same as BalticOI 2012 Day0 A.

Translated by ChatGPT 5