Il y a $n$ boîtes (numérotées de 1 à $n$), $m$ clés (numérotées de 1 à $m$) et $d$ magasins (numérotés de 1 à $d$). La clé $i$ peut être utilisée pour ouvrir l'une des boîtes $a_{i,1}, \dots, a_{i,k_i}$. Cependant, une fois qu'une clé est utilisée pour ouvrir une boîte, elle disparaît. Ainsi, une clé ne peut pas être utilisée pour ouvrir plusieurs boîtes. La clé $i$ est vendue au magasin $s_i$ et son prix est de $c_i$ dollars. Akiba veut acheter certaines clés et ouvrir toutes les boîtes. (Il ne peut pas acheter la même clé plusieurs fois.)

Kitamasa veut empêcher Akiba de faire cela. Pour ce faire, il peut modifier les prix de certaines clés avant qu'Akiba ne décide quelles clés acheter. S'il paie $b_j$ dollars, il peut augmenter le prix de toutes les clés vendues au magasin $j$ d'un dollar. Pour chaque magasin, il peut répéter cette opération un nombre entier non négatif de fois : par exemple, s'il paie $2b_j$ dollars, il peut augmenter le prix de toutes les clés vendues au magasin $j$ de deux dollars. Cependant, par exemple lorsque $b_j = 2$, il ne peut pas payer 1 dollar pour modifier les prix de 0,5 dollar.

L'objectif d'Akiba est de minimiser la valeur (paiement d'Akiba) $-$ (paiement de Kitamasa), et l'objectif de Kitamasa est de la maximiser. Calculez cette valeur lorsque les deux joueurs jouent de manière optimale. Si la réponse peut être infiniment grande, affichez $-1$. Il est garanti que si Kitamasa ne fait rien, Akiba peut ouvrir toutes les boîtes.

Entrée

La première ligne de l'entrée contient trois entiers $n$, $m$ et $d$ ($1 \le m \le 1000$, $n \le 100$, $1 \le n, d \le m$).

Ensuite, $m$ lignes suivent, chacune décrivant une clé. Chaque ligne commence par trois entiers : $c_i$, le prix de la clé, $s_i$, le numéro du magasin où la clé est vendue, et $k_i$, le nombre de boîtes que cette clé peut ouvrir. Ensuite, $k_i$ entiers suivent : les numéros de ces boîtes ($1 \le c_i \le 1000$, $1 \le s_i \le d$, $1 \le k_i \le \min(10, n)$, $1 \le a_{i,j} \le n$, et si $j \neq k$, $a_{i,j} \neq a_{i,k}$).

Ensuite, $d$ lignes suivent, chacune contenant un entier $b_i$ ($1 \le b_i \le 1000$).

Sortie

Affichez un entier : la réponse au problème.

Exemples

Entrée 1

3 4 1
2 1 2 1 2
2 1 2 2 3
2 1 2 3 1
3 1 3 1 2 3
5

Sortie 1

6

Entrée 2

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

Sortie 2

-1

Entrée 3

2 3 2
3 1 2 1 2
4 1 1 2
5 2 2 1 2
1
2

Sortie 3

8