Description

Xiaodou signed up for an intelligence contest. He brought $n$ good friends as his cheering group to take part in the contest together. The rules are as follows.

There are $m$ problems in total. Each person has $1$ chance to answer questions. In each attempt, they choose one problem to answer. After answering correctly, they may continue to answer the subsequent problems of this problem, until they answer a problem incorrectly or there is no subsequent problem.

Each problem has a value. At the end of the contest, the reward value that a participant gets is equal to the minimum value among the problems that were not answered by this participant and his cheering group.

Now we know that Xiaodou and his cheering group are very strong and can solve all the problems in this contest.

Xiaodou wants to know, given the information about the problems and their subsequent problems, what is the maximum value he can obtain.

Input Format

The first line contains two integers $n,m$. ($n\leq50,m\leq500$).

The next $m$ lines describe the problems. Line $i+1$ gives the information of problem $i$, in the form $v_i,k_i,a_{i,1},a_{i,2},...,a_{i,k_i}$, where $v_i$ is the value of this problem, $k_i$ is the number of subsequent problems of this problem, and $a_{i,1},a_{i,2},...,a_{i,k_i}$ are the indices of these $k_i$ subsequent problems.

Output Format

If all problems can be answered correctly, output AK. Otherwise, output the maximum reward value that Xiaodou can obtain.

1 3
1 0
2 1 3
3 0

AK

1 6
1 2 2 3
2 1 4
3 1 4
4 1 6
5 0
6 0

5

Hint

For $10\%$ of the testdata, $1<n,m\leq10$.

For $20\%$ of the testdata, $1<n,m\leq100$.

For $100\%$ of the testdata, $1<n\leq50,1<m\leq500,v_i\leq10^9,k_i,a_{i,j}\leq m$.

Translated by ChatGPT 5