시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 148 12 12 37.500%

문제

상근이는 발렌타인 데이를 기념해 여자친구에게 노란 장미 N개를 선물하려고 한다. 상근이네 집 근처에 꽃집의 수는 두 개이다. 두 꽃 집은 발렌타인 대이를 대비해 많은 꽃을 준비했기 때문에, 꽃이 부족한 일은 없다. 하지만, 두 곳 모두 장미를 다발로 묶어서 판다.

첫 번째 꽃집은 장미 A개를 B원에 팔고, 두 번째 꽃집은 C개를 D원에 판다. A, B, C, D는 모두 양의 정수이다. 만약, 장미 N개를 보다 많이 구매하는 것이 정확하게 N개를 구매하는 것 보다 가격이 저렴하면, N개 보다 많이 구매한 다음 남은 장미는 꽃집 점원에게 줄 것이다.

상근이가 장미를 적어도 N개 구매하는데 필요한 최소 금액을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, A, B, C, D가 주어진다. N은 1015를 넘지 않으며, A, B, C, D는 105를 넘지 않는다.

출력

첫째 줄에 장미를 적어도 N개 사는데 필요한 돈의 최소값을 출력한다. 정답은 항상 1018을 넘지 않는다.

예제 입력

22 2 3 10 14

예제 출력

31

힌트

첫 번째 꽃 집에서 꽃 다발 1개, 두 번째 꽃 집에서 2개를 구매한다.

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2012 P1번