Mike and Stamps
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Mike is fond of collecting stamps. He has a lot of rare and unusual ones in his collection. Unfortunately, a few days ago he was fired from his well-paid job.
But he doesn't complain about that, he acts! That's why Mike picked up N stamps from his collection and is going to sell them. He has already placed an announcement on the Internet and got M offers. Each offer can be described as a set of stamps, that the buyer wants to buy. Now Mike needs your help to choose a set of offers, that he should accept.
He can't accept offers partially. Also, as far as Mike has the only copy of each stamp, he can sell one stamp to at most one buyer.
Of course, Mike wants to maximize the number of accepted offers. Help him!
The first line contains two integer N and M, denoting the number of the stamps and the number of the offers.
The next M lines contain the descriptions of the offers. The (i+1)'th line of the input contains the description of the i'th offer and corresponds to the following pattern: Ki Ai, 1 Ai, 2, ..., Ai, Ki. Ki - is the number of the stamps, which the i'th buyer wants to buy, Ai - is the list of the stamps sorted in the ascending order.
Output should contain the only integer, denoting the maximal number of the offers, that Mike can accept.
1 ≤ N ≤ 20,000
1 ≤ M ≤ 20
1 ≤ Ki
Input: 4 3 2 1 2 2 2 3 2 3 4 Output: 2
In the example test Mike should accept the first and the third offer.
|Tags||easy, kostya_by, march14, search|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.