Эта задача посвящена карточной игре Braindead, придуманной 21 февраля 2019 года и отдалённо основанной на другой, неуказанной карточной игре. Впрочем, догадаться, на какой именно, довольно легко.

Есть карты $n$ мастей и $m$ достоинств. Некоторые масти являются козырными. Козырных мастей может быть несколько или не быть вовсе. В отличие от большинства настоящих карточных игр, несколько карт могут одновременно иметь одинаковые масть и достоинство.

Есть два игрока. У каждого есть непустой набор карт, называемый рукой. Оба игрока знают руки друг друга. Карты в руке некоторого игрока называются его картами.

Карта масти $s_1$ достоинства $r_1$ бьёт карту масти $s_2$ достоинства $r_2$, если выполняется одно из следующих условий:

1. $s_1 = s_2$ и $r_1 > r_2$.
2. $s_1$ — козырная масть, а $s_2$ — нет.

Один игрок — атакующий, другой — защищающийся. Выполняются следующие шаги:

1. Атакующий начинает раунд, играя одну из своих карт. Это называется начальной атакой.
2. Защищающийся играет одну из своих карт, которая бьёт последнюю карту атакующего. Если такой карты нет, защищающийся проигрывает.
3. Атакующий играет одну из своих карт, достоинство которой равно достоинству какой-либо карты, ранее сыгранной любым из игроков. Если такой карты нет, атакующий проигрывает.
4. Перейти к шагу 2.

Игрок не может сыграть одну и ту же карту дважды.

Сколько существует начальных атак, после которых атакующий выигрывает, если далее, после начальной атаки, оба игрока играют оптимально? Начальные атаки разными картами одинаковых масти и достоинства считаются различными.

Входные данные

Первая строка содержит два целых числа $n$ и $m$ ($1 \le n, m \le 18$) — количество мастей и достоинств соответственно.

Вторая строка содержит $n$ целых чисел $t_i$ ($0 \le t_i \le 1$). $t_i$ равно $1$, если $i$-я масть козырная, и $0$, если она обычная (некозырная).

Следующие $n$ строк описывают руку атакующего. В $i$-й из них содержится $m$ целых чисел $a_{i,j}$ ($0 \le a_{i,j} \le 10^{12}$). $a_{i,j}$ равно количеству карт масти $i$ достоинства $j$ у атакующего.

Следующие $n$ строк описывают руку защищающегося в том же формате.

Гарантируется, что руки обоих игроков непусты.

Выходные данные

Выведите одно целое число — количество выигрышных начальных атак.

Примеры

Входные данные 1

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

Выходные данные 1

0

Входные данные 2

3 1
0 1 0
1
0
1
0
1
0

Выходные данные 2

2

Входные данные 3

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

Выходные данные 3

15

Входные данные 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

Выходные данные 4

97

Входные данные 5

1 2
0
4294967296 0
0 2147483647

Выходные данные 5

4294967296