Ця задача присвячена картковій грі 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