Problem Background

NOIP 2016 Popular Group T1

Problem Description

Teacher P needs to buy $n$ pencils as gifts for the children participating in NOIP. She found that there are $3$ types of pencil packages in the store, and the number of pencils and prices in different packages may vary. To be fair, Teacher P decided to buy only one type of pencil package.

Since the store does not allow opening the packages, Teacher P may need to purchase more than $n$ pencils to have enough gifts for the children.

Now, Teacher P wants to know how much money she needs to spend at a minimum to buy at least $n$ pencils, assuming there is enough stock of each package in the store.

Input Format

The first line contains a positive integer $n$, representing the number of pencils needed.

The next three lines describe one type of pencil package each, with two positive integers: the first integer indicates the number of pencils in this package, and the second integer indicates the price of this package.

It is guaranteed that all $7$ numbers are positive integers not exceeding $10000$.

Output Format

One integer, indicating the minimum amount of money Teacher P needs to spend.

57
2 2
50 30
30 27

54

9998
128 233
128 2333
128 666

18407

9999
101 1111
1 9999
1111 9999

89991

Hints

The three types of pencil packages are:

• $2$ pencils per pack, price $2$;
• $50$ pencils per pack, price $30$;
• $30$ pencils per pack, price $27$.

Teacher P needs to purchase at least $57$ pencils.

If she chooses to buy the first package, she needs to buy $29$ packs, totaling $2 \times 29 = 58$ pencils, costing $2 \times 29 = 58$.

In fact, Teacher P will choose to buy the third package, needing to buy $2$ packs. Although she will end up with $60$ pencils ($30 \times 2$), the cost will reduce to $27 \times 2 = 54$, which is less than the first option.

For the second package, although the price per pencil is the lowest, she must buy $2$ packs to have enough pencils, leading to a total cost of $30 \times 2 = 60$. Therefore, Teacher P will not choose this option.

So the final output is $54$.

Data Range

It is guaranteed that all $7$ numbers are positive integers not exceeding $10000$.

Subtasks

Subtasks will provide characteristics of certain test data. If you encounter difficulties solving the problem, you may try to solve only a portion of the test data.

The characteristics of the data scale for each test case are as follows:

In the above table, "integer multiples" means that if it is $K$, the corresponding number of pencils $n$ is guaranteed to be an integer multiple of the quantity of pencils in each package (meaning that it is possible to buy exactly the required number of pencils without buying extra).