本題涉及一種名為 Braindead 的紙牌遊戲，這個遊戲於 2019 年 2 月 21 日發明，並鬆散地借鑑了另一種未指明的紙牌遊戲。不過，要猜出是哪一種並不難。

牌有 $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$）。若第 $i$ 種花色為王牌花色，則 $t_i$ 等於 $1$；若是普通花色（非王牌花色），則等於 $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