Bipartite Blanket

In a bipartite graph the vertices are split into two disjoint sets $A$ and $B$, and every edge joins one vertex of $A$ with one vertex of $B$. A matching $M$ is a set of edges in which no two edges share a vertex. A matching $M$ blankets a set of vertices $V$ when every vertex of $V$ is an endpoint of some edge of $M$.

You are given a bipartite graph in which every vertex carries a positive integer weight. The weight of a set of vertices is the sum of the weights of its vertices.

You are also given an integer threshold $t$. Count the sets of vertices $V$ whose weight is at least $t$ and which are blanketed by at least one matching. Here $V$ is a subset of $A \cup B$, and two different subsets count separately.

The first line contains the number of vertices $n$ in $A$ and the number of vertices $m$ in $B$, separated by a space ($1 \le n, m \le 20$). The vertices of $A$ are $a_1, a_2, \dots, a_n$ and the vertices of $B$ are $b_1, b_2, \dots, b_m$.

Each of the next $n$ lines contains $m$ characters that describe the edges. The $j$-th character of the $i$-th line is 1 if there is an edge between $a_i$ and $b_j$, and 0 otherwise.

The next line contains $n$ integers $v_1, v_2, \dots, v_n$ ($1 \le v_k \le 10\,000\,000$), where $v_k$ is the weight of $a_k$. The line after that contains $m$ integers $w_1, w_2, \dots, w_m$ ($1 \le w_k \le 10\,000\,000$), where $w_k$ is the weight of $b_k$.

The last line contains the integer $t$ ($1 \le t \le 400\,000\,000$).

Print on one line the number of vertex sets whose weight is at least $t$ and that are blanketed by some matching.

In the first example the subset $\{a_1, a_2, b_2, b_3\}$ is blanketed by the matching $\{(a_1, b_2), (a_2, b_3)\}$ and has weight 21. The subsets $\{a_3, b_2, b_3\}$ and $\{a_2, a_3, b_2, b_3\}$ are both blanketed by the matching $\{(a_2, b_3), (a_3, b_2)\}$ and have weights 21 and 23. Every other subset either weighs less than 21 or is blanketed by no matching. For instance $\{a_2, a_3, b_1, b_3\}$ has weight 26, but no matching blankets it, so it is not counted.