本题关于一款名为 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