Załóżmy, że jesteś Li Hua.

Jako wybitny humanista, ostatnio zgłębiałeś tajniki elektrotechniki.

Dysponujesz nieskończoną liczbą ładunków punktowych o ładunku $+e$ i wystarczająco dużej energii kinetycznej. Musisz wprowadzić część z nich do maszyny i wyprowadzić taką samą liczbę ładunków. Zmaksymalizuj sumę energii kinetycznych ładunków po zakończeniu pracy maszyny.

Maszynę można przedstawić jako $n$ węzłów, gdzie potencjał elektryczny $i$-tego węzła wynosi $h_i \,\mathrm{V}$.

W $i$-tym węźle znajduje się $p_i$ kanałów wejściowych, przez które można wprowadzić ładunek. W całym procesie przez każdy kanał można wprowadzić maksymalnie jeden ładunek. Wprowadzenie ładunku przez $j$-ty kanał wymaga wykonania pracy przeciwko siłom zewnętrznym o wartości $a_{i,j} \,\mathrm{eV}$.

W $i$-tym węźle znajduje się $q_i$ kanałów wyjściowych, przez które można wyprowadzić ładunek. W całym procesie przez każdy kanał można wyprowadzić maksymalnie jeden ładunek. Wyprowadzenie ładunku przez $j$-ty kanał wymaga wykonania pracy przeciwko siłom zewnętrznym o wartości $b_{i,j} \,\mathrm{eV}$.

Wewnątrz maszyny znajduje się $m$ jednokierunkowych kanałów. $i$-ty kanał łączy węzły $u_i$ oraz $v_i$, co oznacza, że ładunek może zostać przetransportowany z $u_i$ do $v_i$ (bez ograniczeń liczby użyć). Zakładamy, że inne siły wewnątrz maszyny nie wykonują pracy, a Ty możesz sterować trajektorią każdego ładunku wewnątrz maszyny.

Każdy wprowadzony ładunek musi zostać wyprowadzony, a inne siły wewnątrz maszyny nie wykonują pracy. Oznacza to, że jeśli ładunek wejdzie przez $i$-ty kanał węzła $x$ i wyjdzie przez $j$-ty kanał węzła $y$, praca wykonana przez maszynę nad tym ładunkiem wynosi $(h_x - h_y - a_{x,i} - b_{y,j}) \,\mathrm{eV}$.

Oblicz maksymalną sumę przyrostów energii kinetycznej (jednostka: $\mathrm{eV}$).

Wejście

Pierwsza linia zawiera dwie dodatnie liczby całkowite $n, m$.

Następna linia zawiera $n$ liczb całkowitych, gdzie $i$-ta liczba to $h_i$.

Kolejne $m$ linii zawiera po dwie dodatnie liczby całkowite $u_i, v_i$, opisujące jednokierunkowy kanał.

Kolejne $n$ linii: $i$-ta linia zaczyna się od dodatniej liczby całkowitej $p_i$, po której następuje $p_i$ nieujemnych liczb całkowitych, gdzie $j$-ta z nich oznacza $a_{i,j}$.

Kolejne $n$ linii: $i$-ta linia zaczyna się od dodatniej liczby całkowitej $q_i$, po której następuje $q_i$ nieujemnych liczb całkowitych, gdzie $j$-ta z nich oznacza $b_{i,j}$.

Wyjście

Wypisz jedną nieujemną liczbę całkowitą będącą odpowiedzią.

Przykład

Wejście 1

3 4
3 9 2
1 1
2 3
3 3
3 2
1 2
1 0
1 2
1 1
1 2
1 1

Wyjście 1

6

Ograniczenia

Dla $100\%$ danych zapewniamy $1 \le u_i, v_i \le n$ oraz $0 \le m, p_i, q_i, a_{i,j}, b_{i,j}, h_i$. Wartości $a_{i,j}, b_{i,j}, h_i$ są losowane z rozkładem jednostajnym w odpowiednich zakresach, a pozostałe dane są generowane w sposób losowy, który nie ma na celu celowego spowolnienia algorytmów takich jak SPFA.

Własność specjalna A: $|u_i - v_i| = 1$

Własność specjalna B: $m = n - 1, u_i < v_i, v_i = i + 1$

Własność specjalna C: $\min \{u_i, v_i\} \le 4$