Login Register

Problem C: [TJOI2018]智力竞赛

Time Limit: 1 Sec Memory Limit: 256 MB
Submit Solution

Description

小豆报名参加智力竞赛，他带上了 n 个好朋友作为亲友团一块来参加比赛。
比赛规则如下：一共有 m 道题目，每个人都有 1 次答题机会，每次答题为选择一道题目回答，在回答正确后，可以从这个题目的后续题目，直到题目答错题目或者没有后续题目。
每个问题都会代表一个价值，比赛最后的参赛选手获得奖励价值等价于该选手和他的亲友团没有回答的问题中的最低价值。
我们现在知道小豆和他的亲友团实力非常强，能够做出这次竞赛中的所有题目。
小豆想知道在知道题目和后续题目的条件下，他最大能获得价值是多少?

Input

第一行有两个整数 n , m 。
接下来 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} 表示这 i 个题目的后续题目编号。

Output

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

Sample Input

1 3
1 0
2 1 3
3 0

Sample Output

AK

HINT

对于 10\% 的数据， 1\le n,m \leq 10 。
对于 20\% 的数据， 1\le n,m \leq 100 。
对于 100\% 的数据， 1\le n \leq 50,1\le m \leq 500,v_i\leq 10^9,k_i,a_{i,j}\leq m 。