Problem Background

NOIP2016 Junior Group T1

Problem Description

Teacher P needs to buy $n$ pencils for the children participating in NOIP as gifts. She finds that the store has three types of pencil packages, each with different quantities and prices. To ensure fairness, Teacher P decides to buy only one type of package.

The store does not allow the packages to be opened, so Teacher P may need to buy more than $n$ pencils to distribute the gifts.

Now, Teacher P wants to know, given that the store has enough of each type of package, the minimum amount of money needed to buy at least $n$ pencils.

Input Format

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

The next three lines each contain two positive integers describing a type of package: the first integer represents the quantity of pencils in the package, and the second integer represents the price of the package.

All seven numbers are positive integers not exceeding $10000$.

Output Format

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

Sample Input and Output

Sample Input #1

57
2 2
50 30
30 27

Sample Output #1

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

Notes

The three types of pencil packages are:

• $2$ pencils for $2$ dollars;
• $50$ pencils for $30$ dollars;
• $30$ pencils for $27$ dollars.

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

If she chooses the first type of package, she needs to buy $29$ packages, totaling $2 \times 29 = 58$ pencils, and the cost will be $2 \times 29 = 58$ dollars.

In fact, Teacher P will choose the third type of package, requiring $2$ packages. Although this results in more pencils, $30 \times 2 = 60$, the cost is reduced to $27 \times 2 = 54$, which is less than the first type.

For the second type of package, although the price per pencil is the lowest, she needs to buy $2$ packages, resulting in a total cost of $30 \times 2 = 60$, so Teacher P will not choose this option.

Therefore, the final answer is $54$.

Data Range

All seven numbers are positive integers not exceeding $10000$.

Subtasks

Subtasks provide characteristics of some test data. If you encounter difficulties solving the problem, you can try to solve only some of the test data.

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

In the table, "integer multiple" means: if it is $K$, it indicates that the number of pencils needed, $n$, is necessarily an integer multiple of the quantity of pencils in each package (which means it is always possible to avoid buying extra pencils).

Three new Hack data sets were added on December 23, 2022.

见题面 Input 部分

见题面 Output 部分