题目描述

有 $\red N$ 个程序和 $\red M$ 个变量，一个程序能够对于需要的 $\red I$ 个变量($\red {in_1,in_2,in_3,...,in_I}$) 生成 $\red O$ 个变量($\red {out_1,out_2,out_3,„,out_O}$)，并且需要花费 $\red T$ 的时间，一个程序能够运行 当且仅当它需要的 $\red I$ 个变量都被初始化了，并且花费 $\red T$ 的时间运行完之后能够使对应的 $\red O$ 个变量初始化

现在给出这 $\red N$ 个程序和一个目标 $\red t$，要求算出最少的时间使得 $\red t$ 变量被初始化了

时间 从 $\red 0$ 开始

如果不能使得 $\red t$ 这个变量初始化，输出$\red {-1}$

输入格式

第一行一个整数 Test 表示数据组数，接下来 Test 组数据

对于每组数据: 第一行为三个整数 $\red N$,$\red M$,$\red t$,表示的意义如题所述

第二行是一个长度为 $\red M$ 的 $\red {01}$ 串，其中第 $\red i$ 个字符为 $\red 1$ 表示第 $\red i$ 个变量一开始时 就被初始化了

接下来 $\red N$ 行每行描述了一个程序

对于一个程序，其描述为

$\red {T\ I (in_1,in_2,in_3,...,in_I) O (out_1,out_2,out_3,„,out_O)}$

输出格式

共输出 Test 行，每行一个数表示对应数据的答案

样例

输入样例

4
4 5 5 
1 0 0 0 0
2 1 1 1 2 
3 1 1 1 3 
4 1 2 1 4 
1 2 3 4 1 5 
1 2 1 
01
31 1 2 1 1 
3 5 5
1 0 1 0 0  
3 1 1 1 2  
1 1 3 1 4  
3 2 4 2 1 5 
1 3 3 
100 
1 1 1 1 2

输出样例

7 
31 
6 
-1

【数据规模】

对于 $\red {100\%}$的数据，$\red {1<=Test<=10，1<=N,M<=500，1<=t<=M}$;

对于一个程序，$\red {1<=T<=100，1<=I,O<=10，1<=in_i,out_i<=M}$;