Problem C
Buying Books

You are going to buy $N$ books of different kinds (numbered from $1$ to $N$), and are currently checking the different Internet book stores for prices. Each book is sold by at least one book store, and can vary in prices between the different stores. Furthermore, each book store incurs a postage fee if you order from it. Postage may vary between the various book stores, but it is always the same for a book store no matter how many books you decide to order. Compute the smallest amount of money you need to pay for all the books. You may order any number of books from any number of the book stores.

Input

The first line contains two integers $N$ ($1 \le N \le 100$), the number of books to buy, and $M$ $(1 \le M \le 15$), the number of book shops.

Each book shop is then described in the input. A book shop is described first by two integers denoting the number of books $K$ (of the ones you are going to buy) present in the book shop, and the postage fee for the shop. The next $K$ lines each contains two integers: the number of a book present in the book store, and its price.

All prices and the postage fee are in whole Swedish crowns, and do not exceed $10\, 000$. The book prices are always positive, but the postage fee can be free in some stores.

Output

The program should output the smallest amount that the books cost, including the postage fee of all shops you choose to purchase from.

Scoring

Your program will be tested on $5$ cases. Each case is worth $20$ points.

7 4
4 9
1 28
6 45
3 49
4 108
7 49
1 26
2 179
3 54
4 99
5 129
6 45
7 244
5 20
7 249
2 184
5 133
4 109
6 42
1 0
6 43

822