Istnieje $n$ pudełek (ponumerowanych od $1$ do $n$), $m$ kluczy (ponumerowanych od $1$ do $m$) oraz $d$ sklepów (ponumerowanych od $1$ do $d$). Klucz $i$ może zostać użyty do otwarcia jednego z pudełek $a_{i,1}, \dots, a_{i,k_i}$. Jednakże, po użyciu klucza do otwarcia pudełka, klucz znika. Zatem jednego klucza nie można użyć do otwarcia wielu pudełek. Klucz $i$ jest sprzedawany w sklepie $s_i$, a jego cena wynosi $c_i$ dolarów. Akiba chce kupić pewne klucze i otworzyć wszystkie pudełka. (Nie może kupić tego samego klucza wielokrotnie).

Kitamasa chce mu w tym przeszkodzić. W tym celu może zmienić ceny niektórych kluczy, zanim Akiba zdecyduje, które z nich kupić. Jeśli zapłaci $b_j$ dolarów, może zwiększyć ceny wszystkich kluczy sprzedawanych w sklepie $j$ o jednego dolara. Dla każdego sklepu może powtórzyć tę operację dowolną nieujemną całkowitą liczbę razy: na przykład, jeśli zapłaci $2b_j$ dolarów, może zwiększyć ceny wszystkich kluczy sprzedawanych w sklepie $j$ o dwa dolary. Nie może jednak, przykładowo dla $b_j = 2$, zapłacić 1 dolara i zmienić cen o 0,5 dolara.

Celem Akiby jest zminimalizowanie wartości (płatność Akiby) $-$ (płatność Kitamasy), a celem Kitamasy jest jej zmaksymalizowanie. Oblicz tę wartość, zakładając, że obaj gracze grają optymalnie. Jeśli odpowiedź może być nieskończenie duża, wypisz $-1$. Gwarantuje się, że jeśli Kitamasa nie podejmie żadnych działań, Akiba jest w stanie otworzyć wszystkie pudełka.

Wejście

Pierwsza linia wejścia zawiera trzy liczby całkowite $n$, $m$ oraz $d$ ($1 \le m \le 1000$, $n \le 100$, $1 \le n, d \le m$).

Następnie następuje $m$ linii, z których każda opisuje jeden klucz. Każda linia zaczyna się od trzech liczb całkowitych: $c_i$, ceny klucza, $s_i$, numeru sklepu, w którym klucz jest sprzedawany, oraz $k_i$, liczby pudełek, które ten klucz może otworzyć. Następnie następuje $k_i$ liczb całkowitych: numery tych pudełek ($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$, oraz jeśli $j \neq k$, $a_{i,j} \neq a_{i,k}$).

Następnie następuje $d$ linii, z których każda zawiera jedną liczbę całkowitą $b_i$ ($1 \le b_i \le 1000$).

Wyjście

Wypisz jedną liczbę całkowitą: odpowiedź na zadanie.

Przykład

Wejście 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

Wyjście 1

6

Wejście 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

Wyjście 2

-1

Wejście 3

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

Wyjście 3

8