問題文

キュゥべえはワルプルギスの夜に向けて魔女の合成に明け暮れている．ワルプルギスの夜のために，特別なグリーフシード (魔女の卵) を使って手に入れやすい魔女をうまく合成し目的である舞台装置の魔女を創り上げなければならないからである．

キュゥべえは手に入れやすい種類の魔女のグリーフシードから魔女の素となるものを取り出し，空の特別なグリーフシードに入れることで，そのグリーフシードに魔女を宿らせることができる．また，この世界には，ある組み合わせで複数の魔女を合成すると新たな 1 つの魔女を生み出すことができるという合成法則がいくつかある．そこで，いくつかの特別なグリーフシードを使い，それらの中にある魔女の素となるものを合成し，1 つの特別なグリーフシードに新たな魔女を宿らせることができる．また，合成した結果空となった特別なグリーフシードは再利用することができる．例えば，3 個の特別なグリーフシードに入った魔女を合成すると，それらの 3 個のグリーフシードは，新たな魔女が宿った 1 個の特別なグリーフシードと 2 個の空の特別なグリーフシードとなる．しかし，同じ種類の魔女を同時に複数のグリーフシードに入れることは出来ない．

キュゥべえは魔女の特別なグリーフシードへの寄宿と魔女の合成を繰り返すことにより舞台装置の魔女を創りだしたい．舞台装置の魔女を創りだすにはいくつの特別なグリーフシードが必要か求めよ．

入力形式

入力は以下のような形式で与えられる．

N\ E\ T\\
W_1\ W_2\ …\ W_N\\
G_1\ C_1\ S_{1,1}\ S_{1,2}\ …\ S_{1,C_1}\\
G_2\ C_2\ S_{2,1}\ S_{2,2}\ …\ S_{2,C_2}\\
…\\
G_E\ C_E\ S_{E,1}\ S_{E,2}\ …\ S_{E,C_E}\\

N は魔女の種類の個数，E は合成法則の個数，T は舞台装置の魔女の番号である．W_i は i 番目の魔女が手に入れやすい魔女であるかどうかを表し，1 ならば手に入れやすい魔女であり，0 ならば手に入れやすい魔女ではない．

続く E 行に合成法則が次のように表される：「番号が S_{i,1}\ S_{i,2}\ …\ S_{i,C_i} の魔女を合成することによって G_i の番号の魔女が得られる．」

出力形式

舞台装置の魔女を創りだすのに最低限必要な特別なグリーフシードの個数を出力せよ．創りだすことができない場合は -1 を出力せよ．

制約

• 1 \lt N \leq 300
• 0 \leq E \leq 1000
• 1 \leq T \leq N
• 0 \leq W_i \leq 1\ (1 \leq i \leq N)
• 1 \leq G_i \leq N\ (1 \leq i \leq E)
• 2 \leq C_i \leq 10\ (1 \leq i \leq E)
• 1 \leq S_{i,j} \leq N\ (1 \leq i \leq E,\ 1 \leq j \leq C_i)
• \{G_i, S_{i,1}\ S_{i,2}\ …\ S_{i,C_i}\} は全て異なる．
• 入力中に同一の合成法則が 2 回以上現れることはない．

入出力例

入力例 1

3 1 3
1 1 0
3 2 1 2

出力例1

2

入力例 2

5 0 1
1 1 1 1 1

出力例 2

1

入力例 3

18 5 1
0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1
1 4 2 3 4 5
2 2 6 7
3 3 8 9 10
4 4 11 12 13 14
5 4 15 16 17 18

出力例 3

5

入力例 4

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

出力例 4

3

入力例 5

13 9 13
1 1 0 1 1 0 1 1 0 1 1 0 0
3 2 1 2
6 2 4 5
9 2 7 8
12 2 10 11
6 2 2 3
9 2 5 6
12 2 8 9
3 2 11 12
13 4 3 6 9 12

出力例 5

5

入力例 6

4 4 4
1 1 0 0
1 2 2 3
2 2 3 1
3 2 1 2
3 3 1 2 4

出力例 6

-1

---

Problem Setter: Flat35

---