codechef 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!

Input

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: K_i A_{i, 1} A_{i, 2}, ..., A_{i, Ki}. K_i - is the number of the stamps, which the i'th buyer wants to buy, A_i - is the list of the stamps sorted in the ascending order.

Output

Output should contain the only integer, denoting the maximal number of the offers, that Mike can accept.

Constraints

1 ≤ N ≤ 20,000

1 ≤ M ≤ 20

1 ≤ K_i

Example

Input:
4 3
2 1 2
2 2 3
2 3 4

Output:
2

Explanation

In the example test Mike should accept the first and the third offer.

今天重做了一下codechef以前的錯題。。結果發現自己真的不在狀態。。

題意：有n張郵票賣。但是顧客可能一次要幾張。。

問你最多可以賣給多少個顧客。每種郵票只有一張。

題解：首先看到顧客最多只有20個。所以就算是枚舉也只是2^20 100w

不會超時。而且首先是計算出每兩個顧客是否沖突。

然後就遞歸枚舉。。加少量的剪枝。。

但是遞歸更新最大值時wa了很多次。後來才發現有一種情況沒更新。。。

#include
#include
#include
using namespace std;
#define ll long long
int stamp[22][20002];
int xy[22][22];
int num[22],n,m,ans,f[22];
int max(int a,int b) {
	return a>b?a:b;
}
int ok(int k,int p) {
	int i,j = 0;
	for(i=0;istamp[p][j]) j++;
		else i++;
	}
	return 1;
}
void make() {
	int i,j;
	for(i=0;i=m) {
	ans = max(ans,len);
	return ;
	}
	for(i=p;i