무대 조명

무대를 따라 프로젝터 $n$대가 설치되어 있고, 왼쪽부터 오른쪽으로 1번부터 $n$번까지 번호가 붙어 있다. $i$번 프로젝터의 출력은 $p_i$이다. 켜진 프로젝터의 출력 합이 $Z$ 이상이면 무대가 밝혀진 것으로 본다.

작동하는 프로젝터는 정해진 커넥터에 연결해야 한다. 커넥터는 총 $k$종이다. $i$번 프로젝터는 출력이 $k_i$개이며, 커넥터 $a_{i,1}, a_{i,2}, \dots, a_{i,k_i}$에 연결해야 한다. 어느 시점에든 한 커넥터에는 프로젝터 한 대만 연결할 수 있다.

각 $i$ ($1 \le i \le n$)에 대해, 번호 $i$부터 $r_i$까지의 프로젝터 중에서 동시에 켤 부분집합을 골라 무대를 밝힐 수 있는 최소의 $r_i$를 구하라.

첫 줄에 정수 $n$, $k$, $Z$가 주어진다 ($1 \le n \le 10^5$, $1 \le k \le 8$, $1 \le Z \le 10^9$). 둘째 줄에 정수 $p_1, \dots, p_n$이 주어진다 ($1 \le p_i \le 10^9$). 이후 $n$개의 줄에 커넥터 정보가 주어진다. $i$번째 줄에는 $k_i$ ($1 \le k_i \le k$)와 서로 다른 정수 $a_{i,1}, \dots, a_{i,k_i}$ ($1 \le a_{i,j} \le k$)가 차례로 적힌다.

$n$개의 줄을 출력한다. $i$번째 줄에는 $r_i$가 존재하면 그 값을, 존재하지 않으면 $-1$을 출력한다.