eolymp
bolt
Try our new interface for solving problems

Roses

Zaman məhdudiyyəti 0.5 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Valentine has decided to congratulate all of his N girlfriends by giving each one a yellow rose. In the nearby flower market yellow roses are sold by exactly two vendors. Each of them has an unlimited amount of roses; however, they sell roses only in bouquets (so you can only buy a certain amount of roses at a time). At the first vendor you can buy a bouquet of A roses for B Euros; at the second vendor – a bouquet of C roses for D Euros. A, B, C, and D are all 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 any of the two lovely salesgirls.

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

Giriş verilənləri

The input file contains exactly one line. The first and only line contains five integers: N, A, B, C, and D; every two consecutive numbers are separated by a single whitespace. The value of N does not exceed 10^15, the values of A, B, C, and D do not exceed 10^5.

Çıxış verilənləri

The output file should contain one line with one natural number – the minimum amount of money in Euros for which Valentine can buy at least N roses. It is known that for all given test cases the correct answer does not exceed 10^18.

Nümunə

Giriş verilənləri #1
5 1 4 3 6
Çıxış verilənləri #1
12
Mənbə BOI-2012