P1909 [NOIP 2016 Junior] Buy Pencils

NOIP 2016 Junior T1.

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.

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

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

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