Description

Teacher P needs to go to the store to buy $n$ pencils as gifts for children participating in NOIP. She finds that the store has $3$ types of packaging; different packages may contain different numbers of pencils, and their prices may also differ. For fairness, Teacher P decides to buy only one type of package.

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

Now Teacher P wants to know, assuming there is sufficient stock for each package type, what is the minimum amount of money needed to buy at least $n$ pencils.

Input Format

The first line contains a positive integer $n$, indicating the required number of pencils.

The next three lines each describe one type of package with $2$ positive integers: the first integer is the number of pencils in that package, and the second integer is the price of that package.

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

Output Format

$1$ 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

Hint

The three package types are:

• $2$-pack, price $2$.
• $50$-pack, price $30$.
• $30$-pack, price $27$.

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

If she chooses the first package type, then she needs to buy $29$ packs, totaling $2 \times 29 = 58$ pencils, and the cost is $2 \times 29 = 58$.

In fact, Teacher P will choose the third package type, in which case she needs to buy $2$ packs. Although the final number of pencils is more, $30 \times 2 = 60$, the cost is reduced to $27 \times 2 = 54$, which is less than the first option.

For the second package type, although the price per pencil is the lowest, to have enough she must buy $2$ packs, and the actual cost reaches $30 \times 2 = 60$, so Teacher P will not choose it.

Therefore, the final output is $54$.

Constraints

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

Subtasks

Subtasks provide characteristics of some testdata. If you find the problem difficult, you can try to solve only part of the testdata.

The data scale and characteristics for each test point are shown in the table below:

In the table above, the meaning of “exact multiple” is: if it is $K$, it means the required number of pencils $n$ is an exact multiple of the number of pencils in each package type (which means you can avoid buying extra pencils).

Three Hack testdata groups were newly added on December 23, 2022.

Translated by ChatGPT 5