JOI-kun decided to go to a nearby stationery shop to buy $N$ pencils.

At the stationery shop, pencils are sold in sets of a fixed number of pencils. Set $X$ contains $A$ pencils for $B$ yen, and Set $Y$ contains $C$ pencils for $D$ yen.

JOI-kun will choose either Set $X$ or Set $Y$ and buy some number of the chosen set. He cannot buy both types of sets. Find the minimum amount of money required to obtain at least $N$ pencils.

Input

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

N A B C D

Output

Output the minimum amount of money required for JOI-kun to obtain at least $N$ pencils.

Constraints

• $1 \le N \le 1000$.
• $1 \le A \le 1000$.
• $1 \le B \le 1000$.
• $1 \le C \le 1000$.
• $1 \le D \le 1000$.

Examples

Input 1

10 3 100 5 180

Output 1

360

Note

JOI-kun wants to obtain $10$ pencils. Set $X$ contains $3$ pencils for $100$ yen, and Set $Y$ contains $5$ pencils for $180$ yen. In this case, if he chooses Set $X$, he needs to buy $4$ sets, which costs $400$ yen. If he chooses Set $Y$, he needs to buy $2$ sets, which costs $360$ yen. Therefore, the minimum amount of money required is the smaller of $400$ yen and $360$ yen, which is $360$ yen.

Input 2

6 2 200 3 300

Output 2

600

Note

In this case, whether he chooses Set $X$ or Set $Y$, the required amount of money is $600$ yen. The minimum amount of money required is $600$ yen.