P6767 [BalticOI 2012/2020] Roses (Day0)

For special reasons, the other $24$ testdata sets of this problem should be submitted [here](https://www.luogu.com.cn/problem/U127462). Valentine always wins.

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).

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

One line with one integer representing the minimum cost.

#### 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](http://www.boi2020.lv/data/tasks/en/day0/roses.pdf). It is the same as BalticOI 2012 Day0 A. Translated by ChatGPT 5