Ce problème porte sur le jeu de cartes Braindead, inventé le 21 février 2019 et vaguement inspiré d’un autre jeu de cartes non précisé. Il est toutefois assez facile de deviner lequel.

Les cartes ont $n$ couleurs et $m$ rangs. Certaines couleurs sont des atouts. Il peut y avoir plusieurs couleurs d’atout, ou aucune. Contrairement à la plupart des vrais jeux de cartes, plusieurs cartes peuvent avoir à la fois le même rang et la même couleur.

Il y a deux joueurs. Chacun possède un ensemble non vide de cartes, appelé sa main. Les deux joueurs connaissent la main de l’autre. Les cartes dans la main d’un joueur sont appelées ses cartes.

Une carte de couleur $s_1$ et de rang $r_1$ bat une carte de couleur $s_2$ et de rang $r_2$ si l’une des conditions suivantes est satisfaite :

1. $s_1 = s_2$ et $r_1 > r_2$.
2. $s_1$ est une couleur d’atout et $s_2$ n’en est pas une.

Un joueur est l’attaquant, l’autre le défenseur. Les étapes suivantes sont exécutées :

1. L’attaquant commence la manche en jouant l’une de ses cartes. C’est l’attaque initiale.
2. Le défenseur joue l’une de ses cartes qui bat la dernière carte jouée par l’attaquant. S’il n’en possède pas, il perd la partie.
3. L’attaquant joue l’une de ses cartes dont le rang est égal à celui d’une carte précédemment jouée par l’un ou l’autre des joueurs. S’il n’en possède pas, il perd la partie.
4. Revenir à l’étape 2.

Un joueur ne peut pas jouer deux fois la même carte.

Combien d’attaques initiales permettent à l’attaquant de gagner, en supposant que les deux joueurs jouent ensuite, après l’attaque initiale, de façon optimale ? Les attaques initiales jouant des cartes distinctes de mêmes rang et couleur sont considérées comme différentes.

Entrée

La première ligne contient deux entiers $n$ et $m$ ($1 \le n, m \le 18$), le nombre de couleurs et de rangs, respectivement.

La deuxième ligne contient $n$ entiers $t_i$ ($0 \le t_i \le 1$). $t_i$ vaut $1$ si la $i$-ème couleur est un atout, et $0$ si c’est une couleur ordinaire (non atout).

Les $n$ lignes suivantes décrivent la main de l’attaquant. La $i$-ème contient $m$ entiers $a_{i,j}$ ($0 \le a_{i,j} \le 10^{12}$). $a_{i,j}$ est le nombre de cartes de couleur $i$ et de rang $j$ que possède l’attaquant.

Les $n$ lignes suivantes décrivent la main du défenseur dans le même format.

Il est garanti que les mains des deux joueurs ne sont pas vides.

Sortie

Affichez un seul entier — le nombre d’attaques initiales gagnantes.

Exemples

Entrée 1

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

Sortie 1

0

Entrée 2

3 1
0 1 0
1
0
1
0
1
0

Sortie 2

2

Entrée 3

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

Sortie 3

15

Entrée 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

Sortie 4

97

Entrée 5

1 2
0
4294967296 0
0 2147483647

Sortie 5

4294967296