Hexer

Byteasar has become a hexer, a slayer of monsters, and now he must return to his hometown Byteburg. The road home leads through a land full of beasts. Luckily its inhabitants, forced to fight monsters for centuries, have mastered blacksmithing: they can forge special swords that are very effective against particular kinds of beasts.

The land is vast: it has many towns connected by many roads. The roads never cross outside towns (some of them are underground passages).

Byteasar knows, for every road, which kinds of monster he may meet on it and how long it takes to walk it. He also knows which towns have blacksmiths and which kinds of monster each blacksmith's swords are effective against. To walk down a road, Byteasar must already own a sword effective against every kind of monster that may appear on that road; a sword is obtained by visiting a town whose blacksmith forges it. He may pass through any town or road as many times as he likes, and he can carry any number of swords.

Byteasar starts in town $1$ carrying no sword and wants to reach Byteburg (town $n$) as fast as possible. Find the minimum total walking time, or report that Byteburg cannot be reached.

The first line contains four integers $n$, $m$, $p$, $k$ ($1 \le n \le 200$, $0 \le m \le 3000$, $1 \le p \le 13$, $0 \le k \le n$): the number of towns, the number of roads, the number of monster kinds, and the number of blacksmiths. Towns are numbered $1$ to $n$; town $1$ is the start and town $n$ is Byteburg. Monster kinds are numbered $1$ to $p$.

The next $k$ lines describe the blacksmiths, one per line. Each line contains $w_i$, $q_i$, and then $q_i$ integers $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$): the town where the blacksmith lives, how many monster kinds his swords are effective against, and those monster kinds in increasing order. A town may contain more than one blacksmith.

The following $m$ lines describe the roads, one per line. Each line contains $v_i$, $w_i$, $t_i$, $s_i$, and then $s_i$ integers $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$): the two towns the road connects, the time to walk it (the same in both directions), how many monster kinds may appear on it, and those monster kinds in increasing order. No two roads connect the same pair of towns.

Print one integer: the minimum total time needed to reach Byteburg. If reaching Byteburg is impossible, print $-1$.

In the sample, Byteasar first walks to town $2$ and obtains a sword effective against monster kind $2$, walks back to town $1$, then goes to town $4$, and finally reaches Byteburg (town $6$). The total time is $2 + 2 + 2 + 18 = 24$.

If, on every route to Byteburg, some road requires a sword that Byteasar can never obtain (because no reachable blacksmith forges it), then Byteburg cannot be reached and the answer is $-1$.