시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.5 초 (추가 시간 없음) 256 MB 7 3 3 100.000%

문제

Valentine has decided to congratulate all of his N female friends by giving each one a yellow rose.

He can buy yellow roses at two places at the nearest flower market. Each of them has an unlimited supply of roses, however, they are sold only in bouquets (so you can buy only a set amount of roses as one unit). At the first place, you can buy a bouquet of A roses for B eur; at the second a bouquet of C roses for D eur, where A, B, C and D are positive integers.

If Valentine can buy more than N roses for a smaller amount of money than buying precisely N roses, he will buy more than N roses and gift the leftover to the lovely salesgirl.

Write a program that calculates the minimum amount of money in eur for which Valentine can buy at least N roses!

입력

Five integers N, A, B, C and D (1 ≤ N ≤ 1015, 1 ≤ A, B, C, D ≤ 105) separated by spaces.

출력

Output a single integer in the only line—the minimum amount of money in eur for which Valentine can buy at least N roses. It is guaranteed that the answer does not exceed 1018.

예제 입력 1

5 1 4 3 6

예제 출력 1

12

Valentine will buy six roses — two bouquets at the second place.

예제 입력 2

22 2 3 10 14

예제 출력 2

31

Valentine will buy one bouquet at the first place and two at the second.