Este problema trata do jogo de cartas Braindead, inventado em 21 de fevereiro de 2019 e vagamente baseado noutro jogo de cartas não especificado. No entanto, é bastante fácil adivinhar qual.

Há cartas de $n$ naipes e $m$ valores. Alguns naipes são trunfos. Pode haver vários naipes de trunfo ou nenhum. Ao contrário da maioria dos jogos de cartas reais, várias cartas podem ter simultaneamente o mesmo naipe e valor.

Há dois jogadores. Cada um possui um conjunto não vazio de cartas, chamado mão. Ambos conhecem a mão um do outro. As cartas na mão de um jogador são chamadas as suas cartas.

Uma carta de naipe $s_1$ e valor $r_1$ vence uma carta de naipe $s_2$ e valor $r_2$ se uma das seguintes condições se verificar:

1. $s_1 = s_2$ e $r_1 > r_2$.
2. $s_1$ é um naipe de trunfo e $s_2$ não é.

Um jogador é o atacante e o outro é o defensor. Ocorrem os seguintes passos:

1. O atacante inicia a ronda jogando uma das suas cartas. Isto chama-se o ataque inicial.
2. O defensor joga uma das suas cartas que vence a última carta jogada pelo atacante. Se não tiver tal carta, perde o jogo.
3. O atacante joga uma das suas cartas cujo valor seja igual ao de alguma carta jogada anteriormente por qualquer um dos jogadores. Se não tiver tal carta, perde o jogo.
4. Volte ao passo 2.

Um jogador não pode jogar a mesma carta duas vezes.

Quantos ataques iniciais permitem ao atacante vencer o jogo, supondo que ambos os jogadores jogam de forma ótima depois do ataque inicial? Ataques iniciais que jogam cartas distintas com o mesmo naipe e valor são considerados diferentes.

Entrada

A primeira linha contém dois inteiros $n$ e $m$ ($1 \le n, m \le 18$), o número de naipes e valores, respetivamente.

A segunda linha contém $n$ inteiros $t_i$ ($0 \le t_i \le 1$). $t_i$ é $1$ se o $i$-ésimo naipe for trunfo e $0$ se for um naipe normal (não trunfo).

As próximas $n$ linhas descrevem a mão do atacante. A $i$-ésima contém $m$ inteiros $a_{i,j}$ ($0 \le a_{i,j} \le 10^{12}$). $a_{i,j}$ é o número de cartas de naipe $i$ e valor $j$ que o atacante possui.

As próximas $n$ linhas descrevem a mão do defensor no mesmo formato.

É garantido que as mãos de ambos os jogadores não estão vazias.

Saída

Imprima um único inteiro — o número de ataques iniciais vencedores.

Exemplos

Entrada 1

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

Saída 1

0

Entrada 2

3 1
0 1 0
1
0
1
0
1
0

Saída 2

2

Entrada 3

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

Saída 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

Saída 4

97

Entrada 5

1 2
0
4294967296 0
0 2147483647

Saída 5

4294967296