呢題講嘅係一隻叫 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