Bipartite Barricade

In a bipartite graph, the vertices can be split into two disjoint sets $A$ and $B$ so that every edge connects a vertex in $A$ with a vertex in $B$. A matching $M$ is a set of edges where no two edges share a vertex. A matching $M$ barricades a vertex set $V$ if every vertex in $V$ is an endpoint of at least one edge in $M$.

Each vertex has an integer weight. The weight of a vertex set is the sum of the weights of its vertices.

Given an integer $t$, count the vertex sets $V$ whose weight is at least $t$ and which are barricaded by at least one matching.

The first line contains natural numbers $n$ and $m$ ($1 \le n, m \le 20$), the number of vertices in sets $A$ and $B$. The vertices are denoted $a_1, \dots, a_n$ and $b_1, \dots, b_m$.

Each of the next $n$ lines contains a string of $m$ characters. 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 the weights $v_1, \dots, v_n$ of $a_1, \dots, a_n$ ($1 \le v_k \le 10000000$).

The next line contains the weights $w_1, \dots, w_m$ of $b_1, \dots, b_m$ ($1 \le w_k \le 10000000$).

The last line contains the natural number $t$ ($1 \le t \le 400000000$).

Print the number of vertex sets with weight at least $t$ that are barricaded by at least one matching.

Explanation of the first sample. The set $\{a_1, a_2, b_2, b_3\}$ is barricaded by the matching $\{(a_1, b_2), (a_2, b_3)\}$ and has weight 21. The sets $\{a_3, b_2, b_3\}$ and $\{a_2, a_3, b_2, b_3\}$ are barricaded by the matching $\{(a_2, b_3), (a_3, b_2)\}$, with weights 21 and 23. All other sets either have weight below 21 or are not barricaded by any matching. For example, the set $\{a_2, a_3, b_1, b_3\}$ has weight 26, but no matching barricades it.