Roses

Time limit1sMemory limit128 MB

Summary

Given two bundle prices for roses, find the minimum cost to buy at least N roses using any combination of bundles from either shop.

Level: Medium6 of 10
Topics: Math, Greedy, Brute force
Solved: No attempts yet

Problem

To celebrate Valentine's Day, Sanggeun wants to give his girlfriend $N$ yellow roses. There are two flower shops near his house, and both have prepared plenty of flowers for Valentine's Day, so roses will never run out. However, both shops sell roses only in bundles.

The first shop sells $A$ roses for $B$ won, and the second shop sells $C$ roses for $D$ won. $A$ , $B$ , $C$ , and $D$ are all positive integers. If buying more than $N$ roses is cheaper than buying exactly $N$ , he can buy more and give the leftover roses to the shop clerk.

Write a program that computes the minimum amount of money Sanggeun needs to buy at least $N$ roses.

Input

The first line contains $N$ , $A$ , $B$ , $C$ , and $D$ , separated by spaces. $N$ does not exceed $10^{15}$ , and $A$ , $B$ , $C$ , and $D$ do not exceed $10^{5}$ .

Output

Print the minimum amount of money needed to buy at least $N$ roses. The answer never exceeds $10^{18}$ .

Hint

In the first example, buying one bundle from the first shop (2 roses, 3 won) and two bundles from the second shop (20 roses, 28 won) yields 22 roses for 31 won.

Examples4

Example 1
Input
```
22 2 3 10 14
```
Expected output
```
31
```
Example 2
Input
```
1 1 1 1 1
```
Expected output
```
1
```
Example 3
Input
```
3 5 1 1 1
```
Expected output
```
1
```
Example 4
Input
```
7 3 5 3 4
```
Expected output
```
12
```