시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB58131120.755%

## 문제

You are the owner of IKEA, and you need to order a large number of bolts B. There is a single bolt manufacturer, but there are multiple companies reselling these bolts in packs (e.g. boxes, pallets). These companies form a directed chain, where each company buys packs from the previous company and combines these into new packs (with, of course, the logo of the company displayed brilliantly).

At first glance, it might seem that these intermediate companies offer no advantage, as they just repack the packs of the previous company into larger packs. However, every company has their own target audience, so they want to sell packs with a specific amount of bolts. Because every company only uses the packs of the previous company, it might not be possible to create a pack that has the exact number of bolts specified. Instead, if a company wants to create a pack which is guaranteed to contain X bolts, it will bundle various packs from the previous company where the displayed amount of bolts on these packs sums to no less than X. If there are multiple such combinations it will pick any from those whose displayed sum is minimal. For a better understanding, see the example below. Note that individual companies have no knowledge of the supply chain other than the pack sizes the previous company offers them.

You realise you can take advantage of this: when a company specifies that a pack has a certain number of bolts, it might in practice contain more! Therefore you start a quest of figuring out which pack has the lowest advertised amount, while still containing at least the number of bolts you need. Thanks to your business relations, you can freely choose the company to buy a pack from, including the manufacturer.

## 입력

• The first line of the input contains an integer 1 ≤ B ≤ 103 giving the number of bolts that you need.
• The second line of the input contains an integer 1 ≤ k ≤ 10 giving the number of companies.
• The next k lines each describe a company. Each line consists of the integers li , n1, n2, . . . , nli meaning that the company i produces 1 ≤ li ≤ 10 types of packages of sizes 0 < n1 < n2 < . . . < nli ≤ 103, respectively.

## 출력

• A single integer giving the smallest size of a package that you can buy which contains at least B bolts no matter how the companies build their packages, or impossible if this cannot be achieved.

310
3
2 40 65
2 100 150
2 300 320

## 예제 출력 1

300

Suppose that we would like to buy B = 310 bolts, and that there are three companies. The manufacturer (company one) sells packs of 40 and 65 bolts. Company two sells packs of 100 and 150 bolts. It cannot get these exact amounts from company one, and instead composes them as 100 ≤ 40 + 65 and 150 ≤ 40 + 40 + 40 + 40.

Next comes company three, offering packs of 300 and 320 bolts. It can assemble its 300-pack using three 100-packs (which we know will actually contain 105 + 105 + 105 = 315 bolts) or using two 150-packs (which we know will actually contain 160 + 160 = 320 bolts). However, for company three either combination is fine, so you do not know how many bolts a pack will actually contain. In this case you assume the worst, i.e. that this pack contains 315 bolts.

For its second pack of 320 bolts, company three will use 100 + 100 + 150 ≥ 320 (which we know really contains 105 + 105 + 160 = 370 bolts). There are other combinations adding up to more than 320, but none achieve the minimum of 350, so we know company three will pick that combination.

Note in particular, that company three does not know that the 150-packs of company two actually contain 160 bolts (otherwise it could compose its 320-pack out of two of these). It only knows the amounts advertised by company two.

The packet of size 300 sold by company three is the smallest advertised packet that contains at least B = 310 bolts, so this is the packet we should buy.

371
3
2 40 65
2 100 150
2 300 320

impossible

90
2
2 20 35
2 88 200

88

91
2
2 20 35
2 88 200

200

## 출처

• 문제를 만든 사람: Ragnar Groot Koerkamp