Minimum Cost for Buying Pencils

P teacher needs to buy n pencils as gifts for children participating in NOIP. The shop offers three kinds of pencil packages, each containing a different number of pencils and priced differently. In order to be fair, P teacher has decided to buy only one type of package. Since the shop does not allow the packages to be opened, she might end up buying more than n pencils.

Assuming that the shop has an unlimited supply of each package, determine the minimum amount of money required to buy at least n pencils. For a package type with a pencils and a price b, the total cost if you buy that package is given by \[ \text{cost} = \left\lceil \frac{n}{a} \right\rceil \times b \] where \(\lceil x \rceil\) denotes the ceiling function.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 10⁹), the number of pencils needed.
Each of the next 3 lines contains two integers a and b (1 ≤ a, b ≤ 10⁹), where a is the number of pencils in that package type and b is the price of that package.

outputFormat

Output a single integer, which is the minimum total cost to purchase at least n pencils.

sample

10
3 5
5 7
2 3

14