Este problema trata del juego de cartas Braindead, inventado el 21 de febrero de 2019 e inspirado vagamente en otro juego de cartas no especificado. Aunque es bastante fácil adivinar cuál.

Hay cartas de $n$ palos y $m$ valores. Algunos palos son de triunfo. Puede haber varios palos de triunfo o ninguno. A diferencia de la mayoría de los juegos de cartas reales, varias cartas pueden compartir tanto el palo como el valor.

Hay dos jugadores. Cada uno tiene un conjunto no vacío de cartas, llamado mano. Ambos conocen la mano del otro. Las cartas de la mano de un jugador se denominan sus cartas.

Una carta de palo $s_1$ y valor $r_1$ vence a una de palo $s_2$ y valor $r_2$ si se cumple alguna de las siguientes condiciones:

1. $s_1 = s_2$ y $r_1 > r_2$.
2. $s_1$ es un palo de triunfo y $s_2$ no lo es.

Uno de los jugadores es el atacante y el otro es el defensor. Se realizan los siguientes pasos:

1. El atacante inicia la ronda jugando una de sus cartas. Esto se llama el ataque inicial.
2. El defensor juega una de sus cartas que vence a la última carta jugada por el atacante. Si no tiene tal carta, pierde la partida.
3. El atacante juega una de sus cartas cuyo valor sea igual al de alguna carta jugada anteriormente por cualquiera de los dos jugadores. Si no tiene tal carta, pierde la partida.
4. Vuelve al paso 2.

Un jugador no puede jugar la misma carta dos veces.

¿Cuántos ataques iniciales permiten que el atacante gane la partida, suponiendo que ambos jugadores juegan de forma óptima después del ataque inicial? Los ataques iniciales que juegan cartas distintas con el mismo palo y valor se consideran diferentes.

Entrada

La primera línea contiene dos enteros $n$ y $m$ ($1 \le n, m \le 18$), el número de palos y de valores, respectivamente.

La segunda línea contiene $n$ enteros $t_i$ ($0 \le t_i \le 1$). $t_i$ es $1$ si el $i$-ésimo palo es de triunfo, y $0$ si es un palo normal (no de triunfo).

Las siguientes $n$ líneas describen la mano del atacante. La $i$-ésima contiene $m$ enteros $a_{i,j}$ ($0 \le a_{i,j} \le 10^{12}$). $a_{i,j}$ es la cantidad de cartas de palo $i$ y valor $j$ que tiene el atacante.

Las siguientes $n$ líneas describen la mano del defensor con el mismo formato.

Se garantiza que las manos de ambos jugadores no están vacías.

Salida

Imprime un único entero: el número de ataques iniciales ganadores.

Ejemplos

Entrada 1

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

Salida 1

0

Entrada 2

3 1
0 1 0
1
0
1
0
1
0

Salida 2

2

Entrada 3

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

Salida 3

15

Entrada 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

Salida 4

97

Entrada 5

1 2
0
4294967296 0
0 2147483647

Salida 5

4294967296