题目背景

数据已加强。

题目描述

学习 App 里一共有 $N$ 道题。

天数从第 $0$ 天开始编号。每天你可以做若干道题,但只能做「以前推荐过或当天推荐」的题,每道题只可以做一次。第 $0$ 天,推荐系统会推荐 $p$ 道题。

推荐规则如下:

对于第 $i$ 道题,如果它可能被推荐,就会对应一个题目集合 $s_i$。当且仅当你把 $s_i$ 中每一道题都做出来,并且其中有一道题是当天做完的,那么下一天就会推荐第 $i$ 题。

你的目标是做完第 $K$ 道题,问至少要到第几天才能实现?

输入格式

第一行三个整数 $N,K,p$,含义如题目所述。

第二行 $p$ 个整数,表示第 $0$ 天推荐的题的题号。

第三行一个整数 $R$,表示有 $R$ 条推荐规则。

接下来 $R$ 行,每行包含一条规则,格式如下:

一个整数 $v_i$,表示要推荐的题的题号;接着一个整数 $s_i$,表示要使得这道题被推荐一共要做的题目数量;接下来 $s_i$ 个整数 $p_i$,表示要做的每道题。

输出格式

一个整数,表示最少第几天才能做完第 $K$ 题。

如果无论如何第 $K$ 题都无法完成,输出 -1。

样例

5 5 2
1 2
3
3 2 1 2
4 3 1 2 3
5 3 1 3 4

3

1 1 1
1
0

0

7 7 2
1 2
2
3 2 1 2
6 2 1 2

-1

提示

对于 $30\%$ 的数据,保证 $1 \leq N \leq 100$。

对于 $50\%$ 的数据,保证没有环。

对于 $100\%$ 的数据,保证 $1 \le K,s_i,p_i,v_i \le N \le 5\times 10^3$,$0 \leq R \leq 5 \times 10^3$。各规则对应的题目集合互不相同;同一规则内的 $p_i$ 互不相同;各条规则的 $v_i$ 互不相同。