Handlarz złomem podróżuje między $N$ domami, kupując i sprzedając towary. Domy są ponumerowane od $1$ do $N$. Handlarz zajmuje się łącznie $M$ rodzajami towarów, również ponumerowanymi od $1$ do $M$.

Dom numer $i$ chce sprzedać handlarzowi $p_i$ różnych rodzajów towarów, po jednej sztuce każdego z nich. Rodzaje tych towarów to $a_{i,1}, a_{i,2}, \dots, a_{i,p_i}$. Handlarz może wybrać i kupić tylko te towary, które chce.

Ponadto dom numer $i$ jest zainteresowany $q_i$ różnymi rodzajami towarów, o numerach $b_{i,1}, b_{i,2}, \dots, b_{i,q_i}$. Dom numer $i$ kupuje od handlarza wszystkie dostępne sztuki towarów tych rodzajów, którymi jest zainteresowany. Rodzaje towarów, które dom $i$ sprzedaje, oraz rodzaje towarów, którymi jest zainteresowany, są rozłączne.

Koszt zakupu towaru rodzaju $j$ przez handlarza wynosi $s_j$ za sztukę, a zysk ze sprzedaży wynosi $t_j$ za sztukę.

Handlarz zaczyna z zerową liczbą towarów i może odwiedzać $N$ domów w dowolnej kolejności. Każdy dom musi zostać odwiedzony dokładnie raz. Handlarz chce odwiedzić domy w takiej kolejności, aby zmaksymalizować swój zysk po zakończeniu trasy. Towary pozostałe po zakończeniu trasy nie są wliczane do zysku. Jaki jest maksymalny możliwy zysk?

Wejście

W pierwszej linii podano $N$ oraz $M$ oddzielone spacją ($1 \le N \le 18$; $1 \le M \le 100\,000$).

W drugiej linii podano koszty zakupu $s_1, \dots, s_M$ oddzielone spacjami.

W trzeciej linii podano zyski ze sprzedaży $t_1, \dots, t_M$ oddzielone spacjami ($1 \le s_j < t_j \le 10^9$).

Następnie podano $2N$ linii zawierających informacje o każdym domu w kolejności. Informacje o domu $i$ składają się z dwóch linii:

• W pierwszej linii podano $p_i$ oraz $p_i$ liczb całkowitych $a_{i,1}, \dots, a_{i,p_i}$ oddzielonych spacjami. Oznaczają one rodzaje towarów, które dom $i$ sprzedaje.
• W drugiej linii podano $q_i$ oraz $q_i$ liczb całkowitych $b_{i,1}, \dots, b_{i,q_i}$ oddzielonych spacjami. Oznaczają one rodzaje towarów, którymi dom $i$ jest zainteresowany.

$p_i, q_i$ są liczbami całkowitymi nieujemnymi, spełniającymi warunek $0 \le p_i + q_i \le M$.

Dla każdego $i$, liczby $a_{i,1}, \dots, a_{i,p_i}, b_{i,1}, \dots, b_{i,q_i}$ są parami różnymi liczbami całkowitymi z zakresu od $1$ do $M$.

Wyjście

Wypisz maksymalny zysk, jaki można uzyskać odwiedzając $N$ domów w optymalnej kolejności.

Przykład

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

Wyjście 1

5