KALLAX Construction

Time limit1sMemory limit512 MB

Summary

Given a chain of companies that each combine previous pack sizes to reach target sizes, find the smallest advertised pack guaranteeing at least B bolts.

Level: Hard8 of 10
Topics: Dynamic programming, Greedy, Combinatorics, Math
Solved: No attempts yet

Problem

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

At first glance, these intermediate companies might seem to offer no advantage, since they just repack the packs of the previous company into larger packs. However, every company has its own target audience, so it wants to sell packs with a specific number of bolts. Because every company only uses the packs of the previous company, it might not be able to create a pack with exactly the number of bolts specified. Instead, if a company wants to create a pack that is guaranteed to contain X bolts, it bundles various packs from the previous company whose displayed bolt counts sum to no less than X. If there are multiple such combinations, it picks any one among those whose displayed sum is minimal. For a better understanding, see the example below. Each company has no knowledge of the supply chain other than the pack sizes the previous company offers.

You realize 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 to find the pack with the lowest advertised amount that still contains 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.

Input

The first line of the input contains an integer 1 ≤ B ≤ 10^3 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 l_i, n_1, n_2, ..., n_{l_i}, meaning that company i produces 1 ≤ l_i ≤ 10 types of packages of sizes 0 < n_1 < n_2 < ... < n_{l_i} ≤ 10^3, respectively.

Output

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.

Examples4

Example 1
Input
```
310
3
2 40 65
2 100 150
2 300 320
```
Expected output
```
300
```

Example 2

Input

Expected output

impossible

Example 3
Input
```
90
2
2 20 35
2 88 200
```
Expected output
```
88
```
Example 4
Input
```
91
2
2 20 35
2 88 200
```
Expected output
```
200
```