Hexer

바이테아사르(Byteasar)는 몬스터를 사냥하는 헥서(hexer)가 되었고, 이제 고향 바이트버그(Byteburg)로 돌아가려 한다. 집으로 가는 길은 야수로 가득한 땅을 지난다. 다행히 이 땅의 주민들은 수백 년간 몬스터와 싸워 오면서 대장장이 기술을 갈고닦았다. 이들은 특정 종류의 야수에게 매우 효과적인 특수한 검을 만들 수 있다.

이 땅은 매우 넓어서 많은 도시가 있고, 도시들을 잇는 길이 많다. 길은 도시 바깥에서는 서로 교차하지 않는다(일부는 지하 통로이기 때문이다).

바이테아사르는 각 길에서 마주칠 수 있는 몬스터의 종류와 그 길을 걷는 데 걸리는 시간을 모두 알고 있다. 또한 어느 도시에 대장장이가 있는지, 그리고 그 대장장이가 만드는 검이 어떤 종류의 몬스터에게 효과적인지도 알고 있다. 어떤 길을 지나가려면, 그 길에 나타날 수 있는 모든 종류의 몬스터에 대해 효과적인 검을 이미 가지고 있어야 한다. 검은 그 검을 만드는 대장장이가 있는 도시를 방문하면 얻을 수 있다. 도시와 길은 원하는 만큼 여러 번 지날 수 있고, 검은 몇 자루든 지닐 수 있다.

바이테아사르는 검을 하나도 지니지 않은 채 $1$번 도시에서 출발하여, 가능한 한 빨리 바이트버그($n$번 도시)에 도착하려 한다. 도착에 필요한 최소 총 이동 시간을 구하라. 도착이 불가능하면 그 사실을 알려라.

첫째 줄에 네 정수 $n$, $m$, $p$, $k$ ($1 \le n \le 200$, $0 \le m \le 3000$, $1 \le p \le 13$, $0 \le k \le n$)가 주어진다. 각각 도시의 수, 길의 수, 몬스터 종류의 수, 대장장이의 수이다. 도시는 $1$번부터 $n$번까지 번호가 매겨져 있으며, $1$번이 출발 도시, $n$번이 바이트버그이다. 몬스터 종류는 $1$번부터 $p$번까지 번호가 매겨져 있다.

다음 $k$개의 줄에는 대장장이의 정보가 한 줄에 하나씩 주어진다. 각 줄에는 $w_i$, $q_i$, 그리고 $q_i$개의 정수 $r_{i,1} < r_{i,2} < \dots < r_{i,q_i}$ ($1 \le w_i \le n$, $1 \le q_i \le p$, $1 \le r_{i,j} \le p$)가 주어진다. 각각 대장장이가 사는 도시 번호, 그의 검이 효과적인 몬스터 종류의 개수, 그리고 그 몬스터 종류들을 증가하는 순서로 나열한 것이다. 한 도시에 대장장이가 둘 이상 있을 수도 있다.

그다음 $m$개의 줄에는 길의 정보가 한 줄에 하나씩 주어진다. 각 줄에는 $v_i$, $w_i$, $t_i$, $s_i$, 그리고 $s_i$개의 정수 $u_{i,1} < u_{i,2} < \dots < u_{i,s_i}$ ($1 \le v_i < w_i \le n$, $1 \le t_i \le 500$, $0 \le s_i \le p$, $1 \le u_{i,j} \le p$)가 주어진다. 각각 길이 잇는 두 도시, 그 길을 걷는 데 걸리는 시간(양방향으로 같다), 그 길에 나타날 수 있는 몬스터 종류의 개수, 그리고 그 몬스터 종류들을 증가하는 순서로 나열한 것이다. 같은 두 도시를 잇는 길은 둘 이상 존재하지 않는다.

바이트버그에 도착하는 데 필요한 최소 총 시간을 정수 하나로 출력한다. 도착이 불가능하면 $-1$을 출력한다.

예제에서 바이테아사르는 먼저 $2$번 도시로 가서 몬스터 $2$번에게 효과적인 검을 얻고, $1$번 도시로 돌아온 뒤, $4$번 도시를 거쳐 마지막으로 바이트버그($6$번 도시)에 도착한다. 총 시간은 $2 + 2 + 2 + 18 = 24$이다.

바이트버그로 가는 모든 경로 위의 어떤 길이, 도달할 수 있는 어떤 대장장이도 만들지 못하는 검을 요구한다면, 바이트버그에 도착할 수 없으므로 답은 $-1$이다.