You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小豆报名参加智力竞赛，他带上了 $n$ 个好朋友作为亲友团一块来参加比赛。比赛规则如下：

一共有 $m$ 道题目，每个人都有 $1$ 次答题机会，每次答题为选择一道题目回答，在回答正确后，可以继续回答这个题目的后续题目，直到答错题目或者没有后续题目。

每个问题都会有一个价值，比赛最后参赛选手获得的奖励价值等价于该选手和他的亲友团没有回答的问题中的最低价值。

我们现在知道小豆和他的亲友团实力非常强，能够做出这次竞赛中的所有题目。

小豆想知道在知道题目和后续题目的条件下，他最大能获得的价值是多少？

输入格式

第一行有两个整数 $n,m$。（$n\leq50,m\leq500$）

接下来 $m$ 行，第 $i+1$ 行表示编号为 $i$ 的题目的题目信息，格式形如 $v_i,k_i,a_{i,1},a_{i,2},...,a_{i,k_i}$，其中 $v_i$ 表示该题目的价值，$k_i$ 表示这个题目的后续题目个数，$a_{i,1},a_{i,2},...,a_{i,k_i}$ 表示 $k_i$ 个后续题目的编号。

输出格式

如果全部题目都能答对，则输出 AK，否则输出小豆可以获得的最高奖励价值。

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

提示

对于 $10\%$ 的数据，有 $1<n,m\leq10$。

对于 $20\%$ 的数据，有 $1<n,m\leq100$。

对于 $100\%$ 的数据，有 $1<n\leq50,1<m\leq500,v_i\leq10^9,k_i,a_{i,j}\leq m$。