To zadanie dotyczy gry karcianej Braindead, wymyślonej 21 lutego 2019 roku i luźno opartej na pewnej innej, bliżej nieokreślonej grze karcianej. Nietrudno jednak zgadnąć, o jaką grę chodzi.

Karty mają $n$ kolorów i $m$ rang. Niektóre kolory są atutowe. Kolorów atutowych może być kilka albo może nie być żadnego. W przeciwieństwie do większości rzeczywistych gier karcianych wiele kart może mieć jednocześnie ten sam kolor i tę samą rangę.

Jest dwóch graczy. Każdy ma niepusty zbiór kart, zwany ręką. Obaj gracze znają nawzajem swoje ręce. Karty w ręce danego gracza nazywamy jego kartami.

Karta koloru $s_1$ o randze $r_1$ bije kartę koloru $s_2$ o randze $r_2$, jeśli zachodzi jeden z następujących warunków:

1. $s_1 = s_2$ oraz $r_1 > r_2$.
2. $s_1$ jest kolorem atutowym, a $s_2$ nie jest.

Jeden gracz jest atakującym, a drugi obrońcą. Wykonywane są następujące kroki:

1. Atakujący rozpoczyna rundę, zagrywając jedną ze swoich kart. Nazywamy to atakiem początkowym.
2. Obrońca zagrywa jedną ze swoich kart, która bije ostatnią kartę zagraną przez atakującego. Jeśli nie ma takiej karty, przegrywa grę.
3. Atakujący zagrywa jedną ze swoich kart o randze równej randze jakiejś karty zagranej wcześniej przez któregokolwiek gracza. Jeśli nie ma takiej karty, przegrywa grę.
4. Przejdź do kroku 2.

Gracz nie może zagrać tej samej karty dwukrotnie.

Ile jest ataków początkowych, po których atakujący wygrywa grę, zakładając, że później obaj gracze grają optymalnie? Ataki początkowe zagrywające różne karty o tym samym kolorze i randze uznaje się za różne.

Wejście

Pierwszy wiersz zawiera dwie liczby całkowite $n$ i $m$ ($1 \le n, m \le 18$), oznaczające odpowiednio liczbę kolorów i rang.

Drugi wiersz zawiera $n$ liczb całkowitych $t_i$ ($0 \le t_i \le 1$). Jeśli $i$-ty kolor jest atutowy, $t_i$ wynosi $1$; jeśli jest zwykły (nieatutowy), wynosi $0$.

Następne $n$ wierszy opisuje rękę atakującego. W $i$-tym z nich znajduje się $m$ liczb całkowitych $a_{i,j}$ ($0 \le a_{i,j} \le 10^{12}$). $a_{i,j}$ oznacza liczbę kart koloru $i$ o randze $j$ posiadanych przez atakującego.

Następne $n$ wierszy opisuje rękę obrońcy w tym samym formacie.

Zagwarantowano, że ręce obu graczy są niepuste.

Wyjście

Wypisz jedną liczbę całkowitą — liczbę zwycięskich ataków początkowych.

Przykład

Wejście 1

3 2
0 0 1
1 1
1 0
1 0
0 1
0 1
1 1

Wyjście 1

0

Wejście 2

3 1
0 1 0
1
0
1
0
1
0

Wyjście 2

2

Wejście 3

2 4
1 1
5 5 5 0
0 0 0 0
5 5 5 0
0 0 0 10

Wyjście 3

15

Wejście 4

4 13
1 0 1 0
3 2 0 2 0 3 0 0 3 5 2 1 5
3 3 2 2 2 1 0 4 5 1 5 3 3
1 4 4 2 0 3 2 5 2 5 0 5 3
3 5 4 2 3 3 4 2 2 4 3 2 3
4 3 4 9 0 4 0 1 4 0 1 2 5
1 8 8 6 5 1 1 7 2 4 1 3 9
3 7 3 1 8 9 2 0 0 1 9 6 6
4 6 6 7 9 5 3 2 9 5 0 7 8

Wyjście 4

97

Wejście 5

1 2
0
4294967296 0
0 2147483647

Wyjście 5

4294967296