Un ferrailleur parcourt $N$ maisons pour acheter et vendre des marchandises. Chaque maison est numérotée de $1$ à $N$. Il existe au total $M$ types de marchandises, également numérotées de $1$ à $M$.

La maison $i$ souhaite vendre au ferrailleur $p_i$ types de marchandises différents, un exemplaire de chaque. Les types de ces marchandises sont $a_{i,1}, a_{i,2}, \dots, a_{i,p_i}$. Le ferrailleur peut choisir d'acheter uniquement les marchandises qu'il souhaite parmi celles-ci.

De plus, la maison $i$ s'intéresse à $q_i$ types de marchandises différents, notés $b_{i,1}, b_{i,2}, \dots, b_{i,q_i}$. La maison $i$ achète au ferrailleur la totalité des exemplaires disponibles pour chacun de ces types de marchandises. Les types de marchandises que la maison $i$ vend et ceux auxquels elle s'intéresse sont disjoints.

Le coût d'achat pour le ferrailleur d'une marchandise de type $j$ est $s_j$, et son prix de vente est $t_j$.

Le ferrailleur commence sans aucune marchandise et peut visiter les $N$ maisons dans l'ordre de son choix. Chaque maison doit être visitée exactement une fois. Le ferrailleur souhaite visiter les maisons dans un ordre qui maximise son profit total à la fin de sa tournée. Les marchandises restantes après la tournée ne sont pas comptabilisées dans le profit. Quel est le profit maximal qu'il peut obtenir ?

Entrée

La première ligne contient $N$ et $M$ séparés par un espace. ($1 \le N \le 18$; $1 \le M \le 100\,000$)

La deuxième ligne contient les coûts d'achat $s_1, \dots, s_M$ séparés par des espaces.

La troisième ligne contient les profits de vente $t_1, \dots, t_M$ séparés par des espaces. ($1 \le s_j < t_j \le 10^9$)

Les $2N$ lignes suivantes contiennent les informations pour chaque maison, dans l'ordre. Les informations pour la maison $i$ sont données sur deux lignes :

• La première ligne contient $p_i$ et $p_i$ entiers $a_{i,1}, \dots, a_{i,p_i}$ séparés par des espaces. Ils représentent les types de marchandises que la maison $i$ vend.
• La deuxième ligne contient $q_i$ et $q_i$ entiers $b_{i,1}, \dots, b_{i,q_i}$ séparés par des espaces. Ils représentent les types de marchandises auxquels la maison $i$ s'intéresse.

$p_i$ et $q_i$ sont des entiers supérieurs ou égaux à $0$, satisfaisant $0 \le p_i + q_i \le M$.

Pour chaque $i$, les valeurs $a_{i,1}, \dots, a_{i,p_i}, b_{i,1}, \dots, b_{i,q_i}$ sont des entiers distincts compris entre $1$ et $M$.

Sortie

Affichez le profit maximal pouvant être obtenu en visitant les $N$ maisons dans l'ordre optimal.

Exemples

Entrée 1

3 4
2 1 3 4
3 2 5 7
2 2 3
1 4
1 3
2 1 2
2 4 1
0

Sortie 1

5