시간 제한메모리 제한제출정답맞힌 사람정답 비율
0.5 초 (추가 시간 없음) 256 MB123574551.724%

문제

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.

서브태스크

번호배점제한
120

N, A, B, C, D ≤ 1000

280

No further constraints

예제 입력 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.

채점 및 기타 정보

  • 예제는 채점하지 않는다.