Bánh đã quyết định chúc mừng ~N~ bạn nữ của mình bằng cách tặng mỗi người một bông hồng màu vàng. Anh ấy có thể mua hoa hồng vàng ở hai quầy tại chợ hoa gần nhất. Mỗi quầy có nguồn cung cấp hoa hồng vàng không giới hạn, tuy nhiên chúng chỉ được bán theo bó (vì vậy bạn chỉ có thể mua một số lượng hoa hồng vàng nhất định cho một đơn vị). Ở quầy đầu tiên, bạn có thể mua một bó hoa hồng vàng ~A~ với giá ~B~ đồng; ở quầy thứ hai, bạn có thể mua một bó hoa hồng vàng ~C~ với giá ~D~ đồng, trong đó A, B, C và D là các số nguyên dương.

Nếu Bánh có thể mua nhiều hơn ~N~ bông hồng vàng với số tiền nhỏ hơn so với việc mua chính xác ~N~ bông hồng vàng, anh ấy sẽ mua nhiều hơn ~N~ bông hồng và tặng phần còn lại cho cô bán hàng đáng yêu.

Viết chương trình tính số tiền ít nhất tính theo đồng để Bánh có thể mua được ít nhất ~N~ bông hồng vàng!

Input

Dòng duy nhất chứa ~5~ Số nguyên ~N , A, B, C, D~ thỏa ~1 \le N \le 10^{15}, 1 \le A, B, C, D \le 10^5~.

Output

In ra kết quả cần tìm, dữ liệu ra không vượt quá ~10^{18}~

Samples

Sample Input 1

5 1 4 3 6

Sample Output 1

12

Sample Input 2

22 2 3 10 14

Sample Output 2

31