Diese Aufgabe handelt vom Kartenspiel Braindead, das am 21. Februar 2019 erfunden wurde und lose auf einem anderen, nicht näher benannten Kartenspiel beruht. Es ist allerdings ziemlich leicht zu erraten, welches gemeint ist.

Es gibt Karten mit $n$ Farben und $m$ Rängen. Einige Farben sind Trumpffarben. Es kann mehrere Trumpffarben oder gar keine geben. Anders als bei den meisten echten Kartenspielen können mehrere Karten zugleich denselben Rang und dieselbe Farbe haben.

Es gibt zwei Spieler. Jeder besitzt eine nichtleere Menge von Karten, die als Hand bezeichnet wird. Beide Spieler kennen die Hand des jeweils anderen. Die Karten auf der Hand eines Spielers werden seine Karten genannt.

Eine Karte der Farbe $s_1$ mit Rang $r_1$ schlägt eine Karte der Farbe $s_2$ mit Rang $r_2$, wenn eine der folgenden Bedingungen gilt:

1. $s_1 = s_2$ und $r_1 > r_2$.
2. $s_1$ ist eine Trumpffarbe und $s_2$ nicht.

Ein Spieler ist der Angreifer, der andere der Verteidiger. Die folgenden Schritte werden ausgeführt:

1. Der Angreifer beginnt die Runde, indem er eine seiner Karten ausspielt. Dies heißt Anfangsangriff.
2. Der Verteidiger spielt eine seiner Karten aus, die die zuletzt vom Angreifer ausgespielte Karte schlägt. Hat er keine solche Karte, verliert er das Spiel.
3. Der Angreifer spielt eine seiner Karten aus, deren Rang dem Rang irgendeiner zuvor von einem der Spieler ausgespielten Karte entspricht. Hat er keine solche Karte, verliert er das Spiel.
4. Gehe zu Schritt 2.

Ein Spieler kann dieselbe Karte nicht zweimal ausspielen.

Wie viele Anfangsangriffe gibt es, nach denen der Angreifer gewinnt, wenn beide Spieler danach, also nach dem Anfangsangriff, optimal spielen? Anfangsangriffe mit verschiedenen Karten desselben Rangs und derselben Farbe gelten als verschieden.

Eingabe

Die erste Zeile enthält zwei ganze Zahlen $n$ und $m$ ($1 \le n, m \le 18$), die Anzahl der Farben beziehungsweise Ränge.

Die zweite Zeile enthält $n$ ganze Zahlen $t_i$ ($0 \le t_i \le 1$). $t_i$ ist $1$, wenn die $i$-te Farbe Trumpf ist, und $0$, wenn sie eine gewöhnliche Farbe (kein Trumpf) ist.

Die nächsten $n$ Zeilen beschreiben die Hand des Angreifers. Die $i$-te davon enthält $m$ ganze Zahlen $a_{i,j}$ ($0 \le a_{i,j} \le 10^{12}$). $a_{i,j}$ ist die Anzahl der Karten der Farbe $i$ mit Rang $j$, die der Angreifer hat.

Die nächsten $n$ Zeilen beschreiben die Hand des Verteidigers im selben Format.

Es ist garantiert, dass die Hände beider Spieler nichtleer sind.

Ausgabe

Gib eine einzelne ganze Zahl aus — die Anzahl der siegreichen Anfangsangriffe.

Beispiele

Eingabe 1

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

Ausgabe 1

0

Eingabe 2

3 1
0 1 0
1
0
1
0
1
0

Ausgabe 2

2

Eingabe 3

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

Ausgabe 3

15

Eingabe 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

Ausgabe 4

97

Eingabe 5

1 2
0
4294967296 0
0 2147483647

Ausgabe 5

4294967296