Buying Pencils

Problem Source

Luogu P1909

Problem Background

NOIP2016 Popularization Group T1

Problem Description

Teacher P needs to go to the shop to buy n pencils as gifts for the children participating in NOIP. She finds that the shop sells pencils in 3 kinds of packaging; different packages may contain different numbers of pencils and have different prices. For the sake of fairness, Teacher P decides to buy only one kind of packaging.

The shop does not allow pencils to be sold loose (the packaging may not be opened), so Teacher P may need to buy more than n pencils to have enough to give out as gifts.

Now Teacher P wants to know: assuming each kind of packaging is available in sufficient quantity, what is the minimum amount of money she must spend to buy at least n pencils?

Input Format

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

The following three lines each describe one kind of pencil packaging with 2 positive integers: the first integer is the number of pencils in this package, and the second integer is its price.

All 7 numbers are guaranteed to be positive integers not exceeding 10000.

Output Format

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

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

Constraints

All 7 numbers are guaranteed to be positive integers not exceeding 10000.

Subtasks

The subtasks describe some characteristics of the test data. If you have difficulty solving the whole problem, you may try to solve only part of the test data.

The data scale and features of each test point are shown in the table below:

In the table, "exact multiple" means: if the value is K, then the required number of pencils n is guaranteed to be an exact multiple of the number of pencils in each package (meaning you can always buy exactly enough without any extra).

Three groups of hack data were added on 2022-12-23.

Hint

The three kinds of packaging are:

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

Teacher P needs to buy at least 57 pencils.

If she chooses the first kind of packaging, she must buy 29 packs, totalling 2 × 29 = 58 pencils, costing 2 × 29 = 58.

In fact, Teacher P would choose the third kind of packaging, buying 2 packs. Although she ends up with more pencils — 30 × 2 = 60 — her cost drops to 27 × 2 = 54, less than the first kind.

For the second kind of packaging, although the price per pencil is the lowest, to have enough she must buy 2 packs, actually costing 30 × 2 = 60, so Teacher P will not choose it.

In summary, the minimum amount Teacher P needs to spend is 54.