在二分图中，节点被划分为两个不相交的集合 $A$ 和 $B$，使得每条边都连接 $A$ 中的一个节点和 $B$ 中的一个节点。匹配 $M$ 是一组边，其中任意两条边都不共享同一个节点。如果集合 $V$ 中的每个节点都是匹配 $M$ 中至少一条边的端点，我们称匹配 $M$ 覆盖（blankets）了节点集合 $V$。

给定一个二分图，其中每个节点都被赋予一个权重（正整数）。一个节点集合的权重即为该集合中所有节点权重的总和。

给定一个整数阈值 $t$，求满足以下条件的节点集合 $V$ 的数量：$V$ 的权重至少为 $t$，且 $V$ 被至少一个匹配 $M$ 覆盖。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 20$)，分别表示集合 $A$ 和 $B$ 中的节点数量。我们将 $A$ 中的节点记为 $a_1, a_2, \dots, a_n$，将 $B$ 中的节点记为 $b_1, b_2, \dots, b_m$。

接下来的 $n$ 行，每行包含 $m$ 个字符，描述图的边。第 $i$ 行的第 $j$ 个字符如果为 “1”，则表示 $a_i$ 和 $b_j$ 之间有一条边，否则为 “0”。

接下来一行包含 $n$ 个整数 $v_1, v_2, \dots, v_n$ ($1 \le v_k \le 10\,000\,000$)，表示节点 $a_1, a_2, \dots, a_n$ 的权重。接下来一行包含 $m$ 个整数 $w_1, w_2, \dots, w_m$ ($1 \le w_k \le 10\,000\,000$)，表示节点 $b_1, b_2, \dots, b_m$ 的权重。

最后一行包含一个整数 $t$ ($1 \le t \le 400\,000\,000$)，表示权重阈值。

输出格式

输出权重至少为 $t$ 且被至少一个匹配 $M$ 覆盖的节点集合的数量。

样例

样例输入 1

3 3
010
111
010
1 2 3
8 5 13
21

样例输出 1

3

样例输入 2

3 2
01
11
10
1 2 3
4 5
8

样例输出 2

13

说明

在第一个样例中，子集 $\{a_1, a_2, b_2, b_3\}$ 被匹配 $\{(a_1, b_2), (a_2, b_3)\}$ 覆盖，其权重为 21。子集 $\{a_3, b_2, b_3\}$ 和 $\{a_2, a_3, b_2, b_3\}$ 均被匹配 $\{(a_2, b_3), (a_3, b_2)\}$ 覆盖，权重分别为 21 和 23。所有其他子集要么权重小于 21，要么不能被任何匹配覆盖。例如，子集 $\{a_2, a_3, b_1, b_3\}$ 的权重为 26，但它不能被任何匹配覆盖，因此不计入总数。