JOI-kun ha deciso di andare in una cartoleria vicina per comprare $N$ matite.

Nella cartoleria le matite vengono vendute in confezioni contenenti un numero fisso di matite. La confezione $X$ contiene $A$ matite al prezzo di $B$ yen, mentre la confezione $Y$ contiene $C$ matite al prezzo di $D$ yen.

JOI-kun sceglierà la confezione $X$ oppure la confezione $Y$ e acquisterà un certo numero di confezioni del tipo scelto. Non può acquistare entrambi i tipi di confezioni. Trova la somma minima di denaro necessaria per ottenere almeno $N$ matite.

Input

L'input è fornito dallo standard input nel seguente formato.

N A B C D

Output

Stampa la somma minima di denaro necessaria a JOI-kun per ottenere almeno $N$ matite.

Assunzioni

• $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$.

Esempi

Input 1

10 3 100 5 180

Output 1

360

Note

JOI-kun vuole ottenere $10$ matite. La confezione $X$ contiene $3$ matite per $100$ yen e la confezione $Y$ contiene $5$ matite per $180$ yen. In questo caso, se sceglie la confezione $X$, deve acquistare $4$ confezioni, spendendo $400$ yen. Se sceglie la confezione $Y$, deve acquistare $2$ confezioni, spendendo $360$ yen. Pertanto, la somma minima di denaro necessaria è il minore tra $400$ yen e $360$ yen, ovvero $360$ yen.

Input 2

6 2 200 3 300

Output 2

600

Note

In questo caso, sia scegliendo la confezione $X$ sia scegliendo la confezione $Y$, la somma di denaro necessaria è $600$ yen. La somma minima di denaro necessaria è $600$ yen.