You need to buy ~N~ pencils. There are 3 options: each option comes with a pack of ~X~ pencils and costs ~Y~. You have to buy entire packages (i.e. you cannot just buy one from a pack), so it is possible you will end up buying more than ~N~ pencils. Furthermore, you can choose only one from the three options: you cannot buy one pack of first option and buy another pack of second option.

Assuming all three options have infinite supply, what is the minimum cost to buy at least ~N~ pencils?

Input Specification

The first line consists of a positive integer ~n~ denoting the number of pencils to buy.

In the following 3 lines, each line consists of 2 integers ~X,Y~ denoting the number of pencils in the pack and the cost of the pack.

It is guaranteed that all 7 numbers in the input are positive integers at most ~10\,000~.

Output Specification

Output a line with an integer denoting the minimum total cost to buy at least ~N~ pencils.

Sample Input 1

57
2 2
50 30
30 27

Sample Output 1

54

Explanation

The optimal strategy is buy 2 packs of 30 pencils, costing ~2 \times 27 = 54~.

Sample Input 2

9998
128 233
128 2333
128 666

Sample Output 2

18407

Sample Input 3

9999
101 1111
1 9999
1111 9999

Sample Output 3

89991

Scoring

I will use ~X~ to refer to number of pencils in the pack. I don't want to introducde subscripts at the moment.

• For ~20\%~ of test cases, all ~X~ (i.e. number of pencils in the pack) are equal and ~N~ is always a multiple of ~X~.
• For another ~20\%~ of test cases, all the ~X~ are equal..
• For another ~20\%~ of test cases, two among three options have the same amount of pencils in the pack, and ~N~ is a multiple of ~X~ (number of pencils in a pack).
• For another ~20\%~ of test cases, two among three options have the same amount of pencils in the pack.
• For another ~10\%~ of test cases, ~N~ is a multiple of ~X~ for each ~X~.
• For the final ~10\%~ of test cases, there are no additional constraints.

Notice that if ~N~ is always a multiple of the number of pencils in each pack, you don't have to buy extra.